Longest Palindromic Substring
Find the longest stretch of a string that reads the same forwards and backwards. The standard problem for expanding outward from every center. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
You're given a string s. Return the longest substring of s (a contiguous run of characters) that is a palindrome, meaning it reads the same left to right and right to left.
If several palindromes tie for the longest length, any one of them is accepted.
Example 1
- Input
- s = "xracecarq"
- Output
- "racecar"
Example 2
- Input
- s = "abccbade"
- Output
- "abccba"
An even-length palindrome: its center sits between the two c's rather than on a character.
Example 3
- Input
- s = "pqr"
- Output
- "p"
No two neighbors match, so the best is a single character. "q" or "r" is also accepted.
Constraints
- 1 ≤ s.length ≤ 1000
- s contains only lowercase English letters and digits.
Practice
Runs 14 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Longest Palindromic Substring in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Longest Palindromic Substring
Pattern: Expand around center
Checking every substring is wasteful because palindromes have structure: strip the first and last character off a palindrome and what's left is still a palindrome. Flip that around and every palindrome grows outward from its center, one matching pair of characters at a time.
A string of length n has 2n - 1 possible centers: each of the n characters (odd-length palindromes like "aba") and each of the n - 1 gaps between neighbors (even-length ones like "abba"). From each center, push two pointers outward while the characters match. The moment they differ, you've found the longest palindrome at that center, and you never need to look at longer substrings there.
Forgetting the gap centers is the most common bug: "abccba" has no single middle character.
Approach 1: Brute force: test every substring
Generate all O(n²) substrings and check each with a two-pointer palindrome test, keeping the longest. Simple but each check is O(n).
Time O(n³) · Space O(1)
Approach 2: Dynamic programming table
dp[i][j] is true when s[i..j] is a palindrome: single characters are true, pairs are true when the two characters match, and longer ranges are true when s[i] == s[j] and dp[i+1][j-1] is true. Fill by increasing length and track the longest true cell. Faster than brute force, but it allocates an n × n table.
Time O(n²) · Space O(n²)
Approach 3: Expand around every center
For each index i, expand twice: once from (i, i) for odd lengths and once from (i, i + 1) for even lengths. An expand(lo, hi) helper moves lo left and hi right while both are in bounds and s[lo] == s[hi], then returns the bounds of the last match. Keep the widest bounds seen and slice once at the end.
Same time as the DP, but with constant extra space and much less code.
Time O(n²) · Space O(1)
| Approach | Time | Space |
|---|---|---|
| Brute force: test every substring | O(n³) | O(1) |
| Dynamic programming table | O(n²) | O(n²) |
| Expand around every center | O(n²) | O(1) |
Solution code
Try the practice editor first. Both solutions pass every test above.
Longest Palindromic Substring solution in Python
def longest_palindrome(s: str) -> str:
def expand(lo: int, hi: int) -> tuple[int, int]:
while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
lo -= 1
hi += 1
return lo + 1, hi - 1 # bounds of the last match
best_lo, best_hi = 0, 0
for i in range(len(s)):
for lo, hi in (expand(i, i), expand(i, i + 1)):
if hi - lo > best_hi - best_lo:
best_lo, best_hi = lo, hi
return s[best_lo:best_hi + 1]Longest Palindromic Substring solution in JavaScript
function longestPalindrome(s) {
const expand = (lo, hi) => {
while (lo >= 0 && hi < s.length && s[lo] === s[hi]) {
lo--;
hi++;
}
return [lo + 1, hi - 1]; // bounds of the last match
};
let bestLo = 0;
let bestHi = 0;
for (let i = 0; i < s.length; i++) {
for (const [lo, hi] of [expand(i, i), expand(i, i + 1)]) {
if (hi - lo > bestHi - bestLo) {
bestLo = lo;
bestHi = hi;
}
}
}
return s.slice(bestLo, bestHi + 1);
}Common mistakes
- Only expanding from single characters, which misses every even-length palindrome.
- Off-by-one errors when converting the pointers back to a substring: after the loop exits, the palindrome is `s[lo + 1 .. hi - 1]`, not `s[lo .. hi]`.
- Confusing substring with subsequence. The characters must be contiguous.
- Building a new string at every expansion step instead of tracking indices, which adds an extra factor of n.
What interviewers look for
Start from the observation that a palindrome is symmetric around its middle. That is the insight interviewers listen for, because it turns "check every substring" into "grow from every center."
Say out loud that there are 2n - 1 centers and why, then write the expand helper first. Test it on "abba" and "aba" before wiring it into the loop. If asked about anything faster, mention Manacher's algorithm and its O(n) bound, but don't volunteer to code it unless asked; few interviewers expect it.
Follow-up questions
Can you do it in linear time?
Manacher's algorithm does. It inserts separators so every palindrome has odd length, then reuses the radius of the palindrome mirrored across the current rightmost palindrome's center, so each character is expanded past at most once overall. O(n) time and O(n) space.
How would you count all palindromic substrings instead?
Use the same 2n - 1 centers and count each successful expansion step, since every step outward is one more palindrome. O(n²) time, O(1) space.
What about the longest palindromic subsequence, where characters need not be contiguous?
That needs dynamic programming: `dp[i][j]` is the answer for `s[i..j]`, equal to `dp[i+1][j-1] + 2` when the ends match and `max(dp[i+1][j], dp[i][j-1])` otherwise. It is O(n²) time, and the space drops to O(n) if you keep one row at a time.
Companies that ask Longest Palindromic Substring
Longest Palindromic Substring is tagged by 166 companies in our interview dataset. The score shows how often it comes up at each company.
- Fivetran100%
- Extrahop100%
- Icims100%
- Nielsen100%
- Hpe100%
- Cisco99.5%
- Tinkoff93.8%
- Handshake93%
- Iterable93%
- Hsbc92.2%
- Phonepe89.7%
- Zs Associates88.4%
- Dp World87.6%
- Disney87.6%
- Wixcom87.3%
- Pornhub86.5%
- Earnin83.7%
- Epam Systems83.1%
- Zoho82.8%
- TCS82%
- Microsoft80.5%
- Ciklum80%
- Softwire80%
- Cognizant79.9%
and 142 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required