Sliding Window — Longest Palindromic Substring
↗ LeetCode: Longest Palindromic Substring · Medium · pattern chapter →
Asked atAmazonMetaGoogleMicrosoftBloombergAdobe
Return the longest palindromic substring of s.
Example 1 — s="babad" → "bab" or "aba"Example 2 — s="cbbd" → "bb"Example 3 — s="a" → "a"
Constraints — 1 ≤ n ≤ 1000. Brute checks every substring — O(n³) = 10⁹ ops at n=10³ (~20 min). Expand-around-center is O(n²) = 10⁶ ops; Manacher is O(n) = 10³ ops.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Every substring O(n³)
Approach 2 — DP pal[i][j]
O(n²) time and space.
Approach 3 — Expand around each center (canonical)
Insight. A palindrome has an odd or even center — 2n-1 centers total. Expand outward while chars match.
java
String longestPalindrome(String s) {
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
int l1 = expand(s, i, i);
int l2 = expand(s, i, i + 1);
int len = Math.max(l1, l2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
int expand(String s, int l, int r) {
while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) { l--; r++; }
return r - l - 1;
}Execution Trace
Step 1 / 3center=1 (a), expand to bab
Approach 4 — Manacher's O(n)
Sentinels + palindrome-radius array with reuse across mirrored centers.
Complexity — Time O(n²) expand; O(n) Manacher; Space O(1) expand.
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Every substring | O(n³) | O(1) | baseline |
DP pal[i][j] | O(n²) | O(n²) | works |
| Expand around center | O(n²) | O(1) | canonical |
| Manacher | O(n) | O(n) | polish |
When to use which
- Standard interview → expand around center.
- Very large n → Manacher.
- Return count of palindromic substrings → same expand, just count.
AI Study CompanionBeta
Related problems
Was this page helpful?