Longest Palindromic Substring
Given a string ss1 <= s.length <= 1000s
The page gives two solutions, both O(n^2) time.
Example 1
Output: "bab"
Explanation: "aba" has the same length and is also accepted.
Example 2
Output: "bb"
Example 3
Output: "a"
Explanation: no two characters match, so any single character is a palindrome of length 1.
How to Think About It
Step 1: The direct approach
There are about n^2 / 2 substrings, and checking whether one is a palindrome takes up to n comparisons. Checking all of them is O(n^3), close to 10^8 character comparisons when n = 1000. It works but wastes a lot of effort.
Step 2: Palindromes are nested
Strip the first and last characters from a palindrome and what remains is still a palindrome. Turn that around: s[i..j]s[i] == s[j]s[i+1..j-1]
Step 3: Grow from the middle
Every palindrome has a middle. For odd lengths like "aba" it is one character; for even lengths like "abba" it is the gap between two equal characters. A string of length n has n character centers and n - 1 gap centers.
From a center, step outward while the two ends match. By Step 2, every stretch you pass through is a palindrome, and the first mismatch ends the search, because any longer string around this center would contain that mismatch. This is
Step 4: Or store the answers in a table
Step 2 is also a dynamic programming recurrence. Let isPal[i][j]s[i..j]
Walkthrough
Solution 1 on Example 1, s = "babad"
| center | Character | Odd length | Even length | Best after this center |
|---|---|---|---|---|
| 0 | b | 1 | 0 | "b" |
| 1 | a | 3 ("bab") | 0 | "bab" |
| 2 | b | 3 ("aba") | 0 | "bab", the tie does not replace it |
| 3 | a | 1 | 0 | "bab" |
| 4 | d | 1 | 0 | "bab" |
For Example 2, "cbbd"
Solution 1: Expand Around Center
This method tries all 2n - 1 centers, expands each one while the characters on both sides match, and keeps the longest result.
- Two calls per index:
handles odd lengths andexpand(s, center, center) handles even lengths. The even call returns 0 when the two characters differ.expand(s, center, center + 1) - The length formula: the loop stops one step past the palindrome on each side, so its length is
, notright - left - 1 .right - left + 1 - Turning a length back into bounds:
andstart = center - (len - 1) / 2 work for both parities. For "bb" at center 1, that gives start 1 and end 2.end = center + len / 2 - Ties: the test
is strict, so the first longest palindrome found is kept, and "babad" returns "bab".len > end - start + 1
A common mistake is to expand only around characters, forgetting the gaps between them. Every even-length palindrome is then missed: "cbbd" returns "c" instead of "bb", and "aaaa" returns "aaa".
public class LongestPalindromicSubstring {
public String longestPalindrome(String s) {
int start = 0;
int end = 0; // best palindrome so far is s[start..end]
for (int center = 0; center < s.length(); center++) {
int odd = expand(s, center, center); // middle is one character
int even = expand(s, center, center + 1); // middle is the gap after it
int len = Math.max(odd, even);
if (len > end - start + 1) {
start = center - (len - 1) / 2;
end = center + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expand(String s, int left, int right) {
while (left >= 0 && right < s.length()
&& s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1; // both ends stopped one step past the palindrome
}
public static void main(String[] args) {
LongestPalindromicSubstring solver = new LongestPalindromicSubstring();
System.out.println(solver.longestPalindrome("babad")); // bab
System.out.println(solver.longestPalindrome("cbbd")); // bb
System.out.println(solver.longestPalindrome("ac")); // a
}
}
Solution 2: Dynamic Programming
This method fills a boolean table where isPal[i][j]s[i..j]
- Short substrings: for lengths 1 and 2 the inside is empty, so matching end characters are enough. The condition
covers both and also keepslen <= 2 from passingi + 1 .j - 1 - Longer substrings:
describes a substring two characters shorter, which an earlier pass of the outer loop has already filled.isPal[i + 1][j - 1] - Recording the answer: within one length,
runs from left to right, and only a strictly longer palindrome replaces the best. So "babad" also returns "bab", matching Solution 1.i - Memory: at the limit n = 1000 the table holds 10^6 booleans, about 1 MB, which is fine here but grows quickly with n.
A common mistake is to fill the table with plain nested loops, ijisPal[i + 1][j - 1]
public class LongestPalindromicSubstringDP {
public String longestPalindrome(String s) {
int n = s.length();
boolean[][] isPal = new boolean[n][n]; // isPal[i][j]: is s[i..j] a palindrome
int bestStart = 0;
int bestLen = 1;
for (int len = 1; len <= n; len++) { // shorter substrings first
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
isPal[i][j] = s.charAt(i) == s.charAt(j) && (len <= 2 || isPal[i + 1][j - 1]);
if (isPal[i][j] && len > bestLen) {
bestStart = i;
bestLen = len;
}
}
}
return s.substring(bestStart, bestStart + bestLen);
}
public static void main(String[] args) {
LongestPalindromicSubstringDP solver = new LongestPalindromicSubstringDP();
System.out.println(solver.longestPalindrome("babad")); // bab
System.out.println(solver.longestPalindrome("cbbd")); // bb
System.out.println(solver.longestPalindrome("ac")); // a
}
}
Complexity
- Solution 1 time: O(n^2). There are 2n - 1 centers, and each expansion can run up to n / 2 steps, as in a string of one repeated letter. Most real strings stop expanding much sooner.
- Solution 1 space: O(1) besides the returned string. Only the indices
,start ,end andleft are kept, whatever the length of the input.right - Solution 2 time: O(n^2). The two loops visit each pair with
exactly once, about n^2 / 2 cells, and each cell needs one comparison and one table lookup.i <= j - Solution 2 space: O(n^2). The
table has n × n entries, even though only the upper half withisPal is used.i <= j
Which One to Use
Prefer expand around center. It has the same O(n^2) worst case, uses no table, and on most strings stops expanding early, so it is usually several times faster. The DP version is worth knowing because the same isPal