Coding · Two pointers
Longest Palindromic Substring
- Reported in several places
- Medium
- 3 sources
Two or more independent public pages, at least one a candidate write-up.
Solve it in the playground, with tests
Given a string, return its longest substring that reads the same forwards and backwards. If several palindromes tie for the maximum length, return the one that starts earliest, and return an empty string for empty input. For "football" the answer is "oo", because "oo" and "ll" both have length 2 and "oo" starts first. The string has at most 1,000 characters.
Restated in our own words, not a quote from Amazon or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: what is the alphabet, and is the match case sensitive? Do I return the substring itself, its length, or its start index? If two palindromes tie for longest, does the interviewer want a particular one, or is any acceptable? What should an empty string return? Is a single character a palindrome of length 1?
I would assume any characters compared exactly, a single character counts as a palindrome, an empty string returns an empty string, and ties go to the leftmost palindrome so the answer is deterministic. With at most 1,000 characters, a quadratic solution is comfortably fast.
Brute force
Say the obvious answer and why it is too slow.
Try every substring, test each one for being a palindrome, and keep the longest. There are about n²/2 substrings, and a palindrome test compares up to half of the characters, so the total work is cubic in n.
For 1,000 characters that is already around a hundred million character comparisons, which is acceptable only because the limit is so small. If the limit moved to 5,000 it would be more than ten billion, and the approach would fail. It also repeats work: testing "abcba" re-checks "bcb" and "c" from scratch, even though we just learned that they are palindromes.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n³)
- Time
- O(n²)
- Space
- O(1) extra
Every palindrome has a centre. For an odd length the centre is a character; for an even length it is the gap between two characters. A string of n characters has n odd centres and n - 1 even centres, so 2n - 1 centres in total.
Reverse the thinking: instead of testing substrings, grow a palindrome outward from each centre. Start with a window that is empty or one character wide, then repeatedly compare the character just outside the window on each side. If they match, the bigger window is also a palindrome, because a string whose two ends match and whose inside is a palindrome is itself a palindrome. The moment they differ, or we hit an end of the string, the window cannot grow any further at this centre. Whatever we have is the longest palindrome around that centre.
Correctness follows from two facts. Any palindrome in the string is centred somewhere, and we try every centre. And at a fixed centre the palindromes are nested, so the first mismatch ends them all. We keep the best window seen. To return the leftmost on ties, we only replace the best when a window is strictly longer, and since centres are visited from left to right, an earlier centre means an earlier start for equal lengths.
Each expansion costs O(n) at worst, and there are 2n - 1 centres, so the time is O(n²) with O(1) extra memory. The dynamic programming table needs O(n²) memory for the same time, and Manacher's algorithm reaches O(n). I name the pattern out loud: "expand around the centre, over odd and even centres".
Walk it through
A dry run on the example, step by step.
| Centre | Odd window | Even window | Best so far |
|---|---|---|---|
| 0 (f) | f | (empty) | f |
| 1 (o) | o | oo | oo |
| 2 (o) | o | (empty) | oo |
| 3 (t) | t | (empty) | oo |
| 4 (b) | b | (empty) | oo |
| 5 (a) | a | (empty) | oo |
| 6 (l) | l | ll | oo |
| 7 (l) | l | (none) | oo |
Open on the whiteboardDraws the structure and its pointers for every row of this dry run, one step at a time.
Take "football". At each centre the table shows the odd palindrome and the even palindrome that grows from the gap just after it. Centre 0 gives "f", and the best becomes "f". The interesting row is centre 1: its even expansion compares o with o and matches, then compares f with t and stops. That is a window of length 2, "oo", strictly longer than "f", so it becomes the best.
Centres 2 to 5 produce only single letters. At centre 6 the even expansion matches l with l, giving "ll", but that has the same length as "oo", and a tie does not replace the best, so the earlier palindrome stays. This is how the leftmost rule falls out of a strict comparison. Notice that both two-letter palindromes sit in a gap between letters; skipping the even centres is the usual bug.
The code
Runnable JavaScript, checked against test cases.
function longestPalindrome(text) {
let bestStart = 0;
let bestLength = 0;
function expand(left, right) {
while (left >= 0 && right < text.length && text[left] === text[right]) {
left--;
right++;
}
const length = right - left - 1;
if (length > bestLength) {
bestLength = length;
bestStart = left + 1;
}
}
for (let centre = 0; centre < text.length; centre++) {
expand(centre, centre);
expand(centre, centre + 1);
}
return text.slice(bestStart, bestStart + bestLength);
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Empty string: the loop never runs, the best length stays 0, and the slice returns an empty string. One character: its odd expansion gives length 1. All characters equal, like "aaaa": the centre in the middle of the string expands to the full length, and the odd and even expansions around it both stay in bounds because the loop checks the indexes first.
No repeated letters: every answer has length 1, and the strict comparison keeps the first character, which satisfies the leftmost rule. A palindrome touching either end of the string: the bounds check stops the expansion before reading outside the string. Two equal-length answers, as in "football" where "oo" and "ll" tie: the earlier centre wins, giving "oo".
Follow-ups to expect
Where the interviewer pushes next.
- How would you solve it with a dynamic programming table, and what does it cost in memory?
- Can you reach O(n) time, and what does Manacher's algorithm track?
- How would you count all palindromic substrings instead of finding the longest?
- How would you find the longest palindromic subsequence, which is a different problem?
- What changes if the string is a stream and you must answer after each character?
Where candidates slip
The mistakes this problem punishes.
The most common slip is expanding only around single characters, which misses every even-length palindrome such as "abba". Next is the off-by-one when the loop ends: the window is one step too wide, so the length is right - left - 1 and the start is left + 1.
Candidates also read outside the string by checking the characters before the bounds, replace the best on ties and break the leftmost rule, or build substrings with slice inside the loop, which quietly adds a factor of n. Another trap is describing the solution as dynamic programming and then writing the centre expansion; be clear that it is the centre idea, with the table as a different option.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.