In this tutorial, I will demonstrate how to find the longest palindromic substring in Java. This is a popular string-based coding interview problem that helps you understand string manipulation, two-pointer techniques, and dynamic programming.
A palindrome is a sequence of characters that reads the same forward and backward. For example, "madam", "racecar", and "level" are palindromes.
The longest palindromic substring problem asks you to find the longest continuous portion of a given string that forms a palindrome. For example, in the string "babad", both "bab" and "aba" are valid longest palindromic substrings.
There are several ways to solve this problem. In this tutorial, I will explain the expand-around-center technique, a dynamic programming solution, and a brute-force approach. I will also provide complete Java programs, sample outputs, a dry run, time complexity analysis, and important edge cases.
1. Problem Statement
Write a Java program to find the longest palindromic substring in a given string.
The program should return the actual substring, not just its length.
Example 1
Input: babad Output: Longest Palindromic Substring: bab Length: 3
Explanation: Both "bab" and "aba" are palindromic substrings of length 3. The program returns "bab" because it is the first longest palindrome found.
Example 2
Input: cbbd Output: Longest Palindromic Substring: bb Length: 2
The substring "bb" reads the same forward and backward.
Example 3
Input: forgeeksskeegfor Output: Longest Palindromic Substring: geeksskeeg Length: 10
2. Understanding Palindromic Substrings
A substring is a continuous sequence of characters within a string.
A substring is palindromic when its characters match symmetrically from both ends.
For example:
Palindrome: racecar Forward: r a c e c a r Backward: r a c e c a r
Palindromes can have either odd or even lengths.
Odd-Length Palindromes
An odd-length palindrome has one character at its center.
Examples include:
- aba
- madam
- racecar
For the palindrome "racecar", the center character is 'e'.
Even-Length Palindromes
An even-length palindrome has a center located between two characters.
Examples include:
- aa
- abba
- abccba
For the palindrome "abba", the center lies between the two 'b' characters.
A correct longest-palindromic-substring algorithm must handle both cases.
3. Method 1: Expand Around Center
The expand-around-center technique is one of the most practical solutions to this problem.
The main idea is simple: every palindrome has a center. Starting from that center, you can expand toward both ends as long as the characters match.
For every character position, the algorithm checks two possible centers:
- A single-character center for odd-length palindromes.
- A center between two adjacent characters for even-length palindromes.
During each expansion, the algorithm compares the characters on the left and right sides.
If they match, the current substring remains a palindrome, so the algorithm continues expanding.
If they do not match, expansion stops.
Java Program Using Expand Around Center
public class LongestPalindromicSubstring {
/**
* Finds the longest palindromic substring.
*
* @param str input string
* @return longest palindromic substring
*/
public static String longestPalindrome(String str) {
if (str == null || str.isEmpty()) {
return "";
}
int start = 0;
int end = 0;
for (int i = 0; i < str.length(); i++) {
// Check odd-length palindromes
int oddLength = expandAroundCenter(str, i, i);
// Check even-length palindromes
int evenLength = expandAroundCenter(
str, i, i + 1);
int maxLength = Math.max(
oddLength, evenLength);
// Update when a longer palindrome is found
if (maxLength > end - start + 1) {
start = i - (maxLength - 1) / 2;
end = i + maxLength / 2;
}
}
return str.substring(start, end + 1);
}
/**
* Expands from the center while characters match.
*
* @return length of the palindrome found
*/
private static int expandAroundCenter(
String str, int left, int right) {
while (left >= 0
&& right < str.length()
&& str.charAt(left) == str.charAt(right)) {
left--;
right++;
}
return right - left - 1;
}
public static void main(String[] args) {
String str = "babad";
String result = longestPalindrome(str);
System.out.println("Input String: " + str);
System.out.println(
"Longest Palindromic Substring: " + result);
System.out.println("Length: " + result.length());
}
}Output
Input String: babad Longest Palindromic Substring: bab Length: 3
Note: This implementation treats Java UTF-16 char values as characters and returns the first longest palindrome when multiple results have the same length.
4. Step-by-Step Explanation of the Java Program
Step 1: Handle Null and Empty Strings
if (str == null || str.isEmpty()) {
return "";
}This condition handles null and empty inputs.
If the string contains no characters, there is no nonempty palindromic substring, so the method returns an empty string.
Step 2: Initialize the Substring Boundaries
int start = 0;
int end = 0;The start and end variables store the indexes of the longest palindrome found so far.
Initially, both point to the first character, because every individual character is a palindrome of length 1.
Step 3: Examine Every Possible Center
for (int i = 0; i < str.length(); i++) {The loop visits each character position as a possible palindrome center.
At each position, the algorithm checks odd-length and even-length palindromes.
Step 4: Check Odd-Length Palindromes
int oddLength = expandAroundCenter(str, i, i);Both pointers begin at the same index.
For example, consider "racecar". Starting from the middle character 'e', the algorithm compares characters on both sides and continues expanding while they match.
Step 5: Check Even-Length Palindromes
int evenLength = expandAroundCenter(
str, i, i + 1);For even-length palindromes, the center lies between two adjacent positions.
For example, in "abba", the algorithm starts with the two middle 'b' characters.
It then expands outward to compare the two 'a' characters.
Step 6: Select the Longer Palindrome
int maxLength = Math.max(
oddLength, evenLength);The Math.max() method selects the longer palindrome found around the current center.
Step 7: Update the Longest Substring
if (maxLength > end - start + 1) {
start = i - (maxLength - 1) / 2;
end = i + maxLength / 2;
}If the palindrome found around the current center is longer than the previous result, the algorithm updates its starting and ending indexes.
These formulas work for both odd-length and even-length palindromes.
The comparison uses > rather than >=, so an equally long palindrome does not replace an earlier result.
Step 8: Expand While Characters Match
while (left >= 0
&& right < str.length()
&& str.charAt(left) == str.charAt(right)) {
left--;
right++;
}This loop is the core of the algorithm.
It expands outward as long as:
- The left index remains within the string.
- The right index remains within the string.
- The characters at both indexes are equal.
When any of these conditions becomes false, expansion stops.
Step 9: Calculate the Palindrome Length
return right - left - 1;When the loop finishes, both pointers are positioned just outside the last valid palindrome.
Therefore, subtracting one from the difference gives the correct palindrome length.
Step 10: Extract the Longest Palindrome
return str.substring(start, end + 1);The substring() method extracts the longest palindrome.
Java's substring method excludes the ending index, so the program passes end + 1.
5. Dry Run: Longest Palindromic Substring
Let's walk through the input string:
String: babad Index: 0 1 2 3 4 Char: b a b a d
The algorithm checks each position as a possible center.
| Center Index | Center Character | Longest Odd Palindrome | Longest Even Length | Best Result So Far |
|---|---|---|---|---|
| 0 | b | b | 0 | b |
| 1 | a | bab | 0 | bab |
| 2 | b | aba | 0 | bab |
| 3 | a | a | 0 | bab |
| 4 | d | d | 0 | bab |
At index 1, the algorithm discovers "bab", which has length 3.
At index 2, it discovers "aba", which also has length 3.
Since the program updates the result only when it finds a strictly longer palindrome, "bab" remains the final answer.
Final Output
Longest Palindromic Substring: bab Length: 3
6. Method 2: Find the Longest Palindromic Substring Using Dynamic Programming
Dynamic programming is another approach to solving the longest palindromic substring problem.
The main idea is to store whether each substring is a palindrome and reuse the results when checking longer substrings.
A substring from index i to index j is palindromic when:
- The characters at indexes
iandjare equal. - The substring between those two characters is also a palindrome, unless the substring is short enough that no inner check is needed.
For example, "abba" is a palindrome because its outer 'a' characters match and its inner substring "bb" is also a palindrome.
Java Program Using Dynamic Programming
public class LongestPalindromeDynamicProgramming {
public static String longestPalindrome(String str) {
if (str == null || str.isEmpty()) {
return "";
}
int n = str.length();
boolean[][] dp = new boolean[n][n];
int start = 0;
int maxLength = 1;
// Every single character is a palindrome
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// Check substrings of increasing lengths
for (int length = 2; length <= n; length++) {
for (int i = 0; i + length <= n; i++) {
int j = i + length - 1;
if (str.charAt(i) == str.charAt(j)) {
if (length == 2 || dp[i + 1][j - 1]) {
dp[i][j] = true;
}
}
if (dp[i][j] && length > maxLength) {
start = i;
maxLength = length;
}
}
}
return str.substring(start, start + maxLength);
}
public static void main(String[] args) {
String str = "cbbd";
String result = longestPalindrome(str);
System.out.println("Input String: " + str);
System.out.println(
"Longest Palindromic Substring: " + result);
System.out.println("Length: " + result.length());
}
}Output
Input String: cbbd Longest Palindromic Substring: bb Length: 2
How Dynamic Programming Works
The program creates a two-dimensional boolean array:
boolean[][] dp = new boolean[n][n];Here, dp[i][j] is true when the substring from index i through index j is a palindrome.
First, the program marks every single character as a palindrome.
Next, it checks substrings of length 2, then length 3, and continues until it reaches the full string length.
A longer substring is marked as palindromic when its outer characters match and its inner substring is already known to be a palindrome.
Whenever the program finds a longer palindrome, it updates the starting position and maximum length.
7. Method 3: Brute-Force Approach
The brute-force approach examines every possible substring and checks whether it is a palindrome.
Although this method is less efficient, it is useful for beginners who want to understand the problem before learning optimized solutions.
Java Program Using Brute Force
public class LongestPalindromeBruteForce {
public static boolean isPalindrome(
String str, int left, int right) {
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
public static String longestPalindrome(String str) {
if (str == null || str.isEmpty()) {
return "";
}
int start = 0;
int maxLength = 1;
for (int i = 0; i < str.length(); i++) {
for (int j = i; j < str.length(); j++) {
int currentLength = j - i + 1;
if (currentLength > maxLength
&& isPalindrome(str, i, j)) {
maxLength = currentLength;
start = i;
}
}
}
return str.substring(start, start + maxLength);
}
public static void main(String[] args) {
String str = "babad";
String result = longestPalindrome(str);
System.out.println(
"Longest Palindromic Substring: " + result);
System.out.println("Length: " + result.length());
}
}Output
Longest Palindromic Substring: bab Length: 3
How the Brute-Force Approach Works
- Select every possible starting index.
- Select every possible ending index.
- Check whether the resulting substring is a palindrome.
- If it is longer than the previous best palindrome, update the result.
- Continue until all possible substrings have been considered.
This approach has O(n³) worst-case time complexity because there are O(n²) possible substrings, and checking one substring may require O(n) character comparisons.
8. Time and Space Complexity
Let's compare the three methods.
| Approach | Time Complexity | Auxiliary Space | Recommendation |
|---|---|---|---|
| Expand around center | O(n²) | O(1) | Recommended |
| Dynamic programming | O(n²) | O(n²) | Good alternative |
| Brute force | O(n³) | O(1) | Useful for learning |
Here, n represents the number of UTF-16 code units in the input string.
Why Does Expand Around Center Take O(n²) Time?
There are 2n - 1 possible centers in a string of length n.
Each center can expand across as many as O(n) character positions.
Therefore, the worst-case time complexity is O(n²).
Why Is the Auxiliary Space O(1)?
The expand-around-center algorithm uses only a few integer variables for indexes and lengths.
It does not create a table or collection proportional to the input size.
Therefore, its auxiliary space complexity is O(1), excluding the returned substring.
Why Does Dynamic Programming Require O(n²) Space?
The dynamic programming solution stores palindrome information for pairs of indexes in a two-dimensional boolean array.
For a string of length n, the table contains n × n boolean entries, giving it O(n²) space complexity.
9. Handling Important Edge Cases
Case 1: Empty String
Input: "" Output: Longest Palindromic Substring: "" Length: 0
The program returns an empty string.
Case 2: Single Character
Input: "a" Output: Longest Palindromic Substring: a Length: 1
Every single character is a palindrome.
Case 3: All Characters Are Identical
Input: "aaaaa" Output: Longest Palindromic Substring: aaaaa Length: 5
The entire string is a palindrome.
Case 4: No Palindrome Longer Than One Character
Input: "abcd" Output: Longest Palindromic Substring: a Length: 1
Every individual character is a palindrome, but no longer palindromic substring exists.
Case 5: Even-Length Palindrome
Input: "cbbd" Output: Longest Palindromic Substring: bb Length: 2
Case 6: Odd-Length Palindrome
Input: "racecar" Output: Longest Palindromic Substring: racecar Length: 7
Case 7: Multiple Longest Palindromes
Input: "babad" Output: Longest Palindromic Substring: bab Length: 3
Both "bab" and "aba" have the same maximum length. The provided implementations retain the first result found.
Case 8: Uppercase and Lowercase Characters
Input: "Aba" Output: Longest Palindromic Substring: A Length: 1
The programs compare characters exactly. Therefore, 'A' and 'a' are treated as different characters.
Case 9: Null Input
The programs return an empty string when the input reference is null.
This is a deliberate design choice. In some applications, rejecting null input may be more appropriate.
10. Important Note About Unicode Characters
Java strings use UTF-16 encoding, and charAt() returns a UTF-16 code unit.
Many Unicode characters, including some emoji, use two char values known as a surrogate pair.
Because the programs in this tutorial compare individual char values, they are most suitable for interview problems that treat strings as sequences of UTF-16 code units, particularly examples using ordinary English letters and digits.
If your application needs to recognize complete Unicode code points or grapheme clusters as characters, you must adapt the algorithm to use the appropriate text representation.
11. Common Mistakes to Avoid
Mistake 1: Checking Only Odd-Length Palindromes
A palindrome can have either an odd or an even number of characters.
If you check only single-character centers, you will miss palindromes such as "abba" and "bb".
Always check both types of centers.
Mistake 2: Incorrect Substring Boundaries
The substring() method excludes its ending index.
If end represents an inclusive palindrome boundary, use end + 1 when extracting the result.
Mistake 3: Forgetting to Check Array or String Boundaries
Before calling charAt(), make sure the indexes remain within the valid string range.
Otherwise, the program may throw a StringIndexOutOfBoundsException.
Mistake 4: Confusing Substring and Subsequence
A substring must consist of consecutive characters from the original string.
A subsequence may skip characters.
The longest palindromic substring and longest palindromic subsequence are different problems.
Mistake 5: Using Brute Force for Large Inputs
Brute force may require cubic time in the worst case.
The expand-around-center algorithm is typically preferable because it reduces the worst-case time complexity to O(n²) while using constant auxiliary space.
12. Frequently Asked Questions
Q1. What is the longest palindromic substring?
It is the longest continuous portion of a string that reads the same forward and backward.
Q2. What is the best approach to find the longest palindromic substring in Java?
The expand-around-center technique is a strong general-purpose solution. It uses O(n²) time and O(1) auxiliary space.
Q3. Can I solve this problem using dynamic programming?
Yes. Dynamic programming stores whether each substring is a palindrome and uses those results to identify longer palindromes.
Q4. What is the time complexity of the expand-around-center approach?
Its worst-case time complexity is O(n²).
Q5. Why do I need to check two centers?
Checking (i, i) handles odd-length palindromes, while checking (i, i + 1) handles even-length palindromes.
Q6. Can a string have more than one longest palindromic substring?
Yes. For example, "babad" has two longest palindromic substrings: "bab" and "aba". Both have length 3.
Q7. What is the difference between a palindromic substring and a palindromic subsequence?
A palindromic substring contains consecutive characters. A palindromic subsequence can skip characters while preserving their relative order.
Q8. Is there a faster algorithm than expand around center?
Yes. Manacher's algorithm finds the longest palindromic substring in O(n) time.
However, it is more complex to implement and explain. Expand around center is often preferred for coding interviews unless the interviewer specifically requires a linear-time solution.
13. Conclusion
In this tutorial, you learned how to find the longest palindromic substring in Java using three different approaches.
- Expand around center: Checks odd-length and even-length palindromes using two pointers.
- Dynamic programming: Stores palindrome information for substrings in a two-dimensional table.
- Brute force: Examines candidate substrings and checks whether each one is a palindrome.
For Java coding interviews, I recommend learning the expand-around-center technique first. It provides a good balance between performance, readability, and ease of implementation.
Once you understand this approach, you can explore dynamic programming and Manacher's algorithm for more advanced palindrome problems.
Understanding this problem will also help you solve related interview questions involving palindromic substrings, palindromic subsequences, and two-pointer string algorithms.
14. Official Java Documentation
For additional information about the Java APIs used in this tutorial, refer to the official Oracle documentation:
- Java String Class — Documentation for
charAt(),length(), andsubstring(). - Java Math Class — Documentation for
Math.max(). - Java Character Class — Documentation for Java characters and Unicode-related operations.
- Java Language Specification: Lexical Structure — Details about characters and Unicode processing in Java.
Continue Learning with Java Guides
Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.
By Ramesh Fadatare - Udemy Instructor Partner
Comments
Post a Comment
Leave Comment