LeetCode · #5
Longest Palindromic Substring Solution
Given a string s, return the longest palindromic substring in s.
01
Section One · Problem
Problem Statement
Given string s, return the longest substring that reads the same forwards and backwards. If there are multiple answers of the same length, return any one.
Example
Input: s = "babad" Output: "bab" // "aba" is also valid
Constraints
• 1 ≤ s.length ≤ 1000 • s consists of English letters and digits
02
Section Two · Approach 1
Brute Force — O(n³)
Check every substring (O(n²)) and verify if it's a palindrome (O(n)). Track the longest one found.
Why it works
Exhaustively checking all substrings guarantees the longest palindrome is found.
Why we can do better
Problem: O(n³) is too slow for n=1000. Expand-around-center eliminates the palindrome verification step entirely: starting from each center, expand while characters match, tracking the longest span.
Java — O(n³) brute
class Solution {
public String longestPalindrome(String s) {
String best = "";
for (int i = 0; i < s.length(); i++)
for (int j = i; j < s.length(); j++) {
String sub = s.substring(i, j + 1);
if (sub.length() > best.length() && isPalin(sub))
best = sub;
}
return best;
}
private boolean isPalin(String s) {
int l = 0, r = s.length() - 1;
while (l < r) if (s.charAt(l++) != s.charAt(r--)) return false;
return true;
}
}
Python — O(n³) brute
class Solution:
def longestPalindrome(self, s: str) -> str:
best = "" for i in range(len(s)):
for j in range(i, len(s)):
sub = s[i:j+1]
if len(sub) > len(best) and sub == sub[::-1]:
best = sub
return best
| Metric | Value |
|---|---|
| Time | O(n³) |
| Space | O(1) |
03
Section Three · Approach 2
Expand Around Center — O(n²) time, O(1) space
For each of 2n-1 centers (characters and gaps), expand outward while both sides match. Track the longest palindrome found.
💡 Mental model: Imagine placing a mirror at every position in the string (and between positions). The mirror reflects text symmetrically. You expand the mirror's reach — as long as letters on both sides match, the palindrome grows. The widest mirror gives the longest palindromic substring. You try n character-centers (odd-length) and n-1 gap-centers (even-length) = 2n-1 total mirrors.
Algorithm
- For each index
i: - Expand from
(i, i)for odd-length palindromes. - Expand from
(i, i+1)for even-length palindromes. - Each expansion returns the length of the longest palindrome found at that center.
- Track the start index and length of the global best.
🎯 When to recognize this pattern:
- "Find longest palindromic substring" (not subsequence — that's a different 2D DP).
- Expand-around-center is O(n²) with O(1) space — better than 2D DP table which uses O(n²) space.
- Also used in LC 647 (count all palindromic substrings). Manacher's gives O(n) but is rarely expected.
Why not 2D DP?:
- A 2D table
dp[i][j] = true if s[i..j]is palindrome uses O(n²) space. - Expand-around-center achieves the same time complexity with O(1) space.
- Both are valid in interviews, but expand-around-center is cleaner to code and more space-efficient.
04
Section Four · Trace
Visual Walkthrough
Trace for s = "babad".
Longest Palindromic Substring — Expand Around Center
05
Section Five · Implementation
Code — Java & Python
Java — Expand around center
class Solution {
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++;
}
int len = r - l - 1; // length of palindrome found if (len > maxLen) {
start = l + 1;
maxLen = len;
}
}
}
Python — Expand around center
class Solution:
def longestPalindrome(self, s: str) -> str:
res = "" def expand(l, r):
while l >= 0 and r < len(s) and s[l] == s[r]:
l -= 1; r += 1 return s[l+1:r]
for i in range(len(s)):
odd = expand(i, i)
even = expand(i, i + 1)
if len(odd) > len(res): res = odd
if len(even) > len(res): res = even
return res
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space | Trade-off |
|---|---|---|---|
| Brute force | O(n³) | O(1) | Check every substring — cubic |
| 2D DP table | O(n²) | O(n²) | Same time, extra space for boolean table |
| Expand around center ← optimal | O(n²) | O(1) | No table needed; natural palindrome discovery |
Manacher's O(n) exists but is extremely complex to code correctly. Expand-around-center is the expected interview answer. Know that Manacher's exists as a follow-up mention.
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Input | Why It Matters |
|---|---|---|
| Single char | "a" | The entire string is the palindrome. Return "a". |
| All same | "aaaa" | Entire string is palindromic. Expansion from center(1,1) reaches full string. |
| No multi-char palindrome | "abcd" | Return any single character. |
| Even-length palindrome | "cbbd" | "bb" is the longest. Found via even-center expand (1,2). |
| Entire string palindrome | "racecar" | Center at index 3 expands to full length. |
⚠ Common Mistake: Computing the palindrome length as
r - l + 1 after the while loop. By the time the loop exits, l and r point one step past the palindrome boundaries (to the first mismatch). The correct length is r - l - 1, and the substring is s[l+1..r-1] inclusive.