Longest Palindromic Substring — Expand Around Center
Treat every character and gap as a center, expanding while the ends mirror each other to find the best span.
Problem Statement
Return the longest palindromic substring contained in s.
Why This Problem Matters
- Demonstrates the expand-around-center trick that generalises to many palindrome problems.
- Forces you to handle both even- and odd-length palindromes explicitly.
- Sets up discussion about more advanced techniques like Manacher’s algorithm.
Thought Process
Recognise the structure
Every palindrome mirrors around a center; brute force over all substrings is wasteful when you can grow from centers directly.
Handle two center types
Single characters form odd-length palindromes, adjacent pairs handle even-length ones.
Track the best window
Whenever a longer palindrome appears, recompute start and end boundaries using the current center and length.
Step-by-Step Reasoning
- Initialise start = 0 and end = 0 to track the best window.
- For each index i, expand around (i, i) for odd palindromes and (i, i + 1) for even palindromes.
- Take the longer expansion and update start/end based on its length.
- Return s.substring(start, end + 1) once all centers are checked.
Dry Run
s = "babad", center = 2
Odd expansion around "b" reaches "bab"; start/end become 0 and 2.
s = "cbbd", center = (1,2)
Even expansion yields "bb"; start/end become 1 and 2 for the final answer.
Complexity Analysis
Time
O(n^2)
Space
O(1)
Why
Each expansion can traverse the string once and there are O(n) centers to try.
Annotated Solution
public class LongestPalindromicSubstring {
public String longestPalindrome(String s) {
if (s.length() < 2) {
return s;
}
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i += 1) {
int len1 = expand(s, i, i);
int len2 = expand(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + 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 -= 1;
right += 1;
}
return right - left - 1;
}
}Each index acts as both an odd and even center. Expanding outward while the ends match finds the longest span in constant additional space.
Common Pitfalls
- Forgetting to evaluate the even-length center leaves answers like "bb" undiscovered.
- Incorrectly computing start/end with integer division can shift the window by one.
- Breaking the expansion loop without bounds checks triggers StringIndexOutOfBoundsException.
Follow-Up Questions
- Can you design a linear-time solution using Manacher’s algorithm?
- How would you count the number of palindromic substrings instead of returning one example?