#5
Longest Palindromic Substring
Medium Expand around centre
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return the longest substring that is a palindrome.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the longest piece that is a palindrome.
Why this works: every palindrome grows out from a centre (one letter, or a gap between two). Try every centre and expand while both sides match.
Example: "babad"
centre 'a' (index 1): "bab" length 3centre 'b' (index 2): "aba" length 3answer "bab"
✦Hints open one at a time
Every palindrome has a centre: one character (odd length) or a gap between two (even length).
There are 2n − 1 centres. Expand outward from each while the ends match.
↗Approach
For each index try both centre types, expand while s[l] == s[r], and keep the longest span.
</>Solution (Java)
class Solution {
private int start = 0, maxLen = 0;
public String longestPalindrome(String s) {
for (int i = 0; i < s.length(); i++) {
expand(s, i, i); // odd length
expand(s, i, i + 1); // even length
}
return s.substring(start, start + maxLen);
}
private void expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
l--;
r++;
}
if (r - l - 1 > maxLen) { // the palindrome is l+1 .. r-1
maxLen = r - l - 1;
start = l + 1;
}
}
}!Common mistake
Only expanding around single characters, which misses even-length palindromes like "abba".
Complexity
- Time: O(n²).
- Space: O(1).
Topic: Strings
🎬 Episodes 16–20: video coming soon