Problem overview
The method longestPalindrome(s) receives a string and returns its longest palindromic substring. A palindrome reads the same forward and backward, like "racecar" or "abba". A substring is a run of consecutive characters, so "bcd" is a substring of "abcde" but "ace" is not. When several palindromes share the greatest length, the one that starts furthest to the left wins. Uppercase and lowercase letters are different characters, so "Aa" is not a palindrome.
For "babad" the answer is "bab": "aba" has the same length, but "bab" starts first. For "cbbd" it is "bb", a palindrome of even length. For "abacdfgdcaba" it is "aba", the first of its two appearances.
The lesson asks for O(n²) time and O(1) extra space besides the returned string, where n is the length of s.
Approach: grow palindromes from their centers
Checking every substring on its own takes O(n³): about n²/2 substrings, each up to n characters long. Looking at palindromes from the middle is much cheaper.
Every palindrome has a center: its middle character when the length is odd, or the gap between its two middle characters when the length is even. A string of n characters has 2n - 1 centers, n characters and n - 1 gaps. From a center, expand: put two positions left and right there, and move them one step outward while both are inside the string and their characters are equal. When they stop, the palindrome between them is the longest one around that center, and it has right - left - 1 characters.
A helper does this and returns the length. For each index i it is called twice: with (i, i) for the odd center on s[i], and with (i, i + 1) for the even center in the gap after it. For "babad" the results are:
i odd even start
0 1 0 0
1 3 0 0
2 3 0 1
3 1 0 3
4 1 0 4At i = 1 the longest palindrome has length 3 and starts at index 0: "bab". At i = 2 there is another one of length 3, starting at index 1: "aba". It isn't longer than the best so far, so it doesn't replace it, and the leftmost one stays.
Step by step
- Remember the best palindrome with two variables,
bestStartandbestLen, both 0. Its start and length are all that is needed. The substring is cut out once, at the end. - Visit every position
ifrom 0 tos.length - 1. Each one gives two centers, which together cover all2n - 1(the extra even center after the last character finds nothing). - Odd center. Call
this.expand(s, i, i)and keep the result inodd. The helper is written afterwards; the main loop only needs to know what it returns. - Even center. Call
this.expand(s, i, i + 1)and keep the result ineven. It is 0 when the two characters differ or wheniis the last index. - Take the larger of the two with
Math.max, inlength. - Compare strictly:
length > bestLen. A palindrome equally long starts further right, so it must not replace the one found first. - Compute the start. An odd palindrome of
lengthcharacters has(length - 1) / 2characters before its middles[i]. An even one haslength / 2 - 1characters befores[i], its left middle. Rounded down, both equal(length - 1) / 2, so the start isi - Math.floor((length - 1) / 2). - Update
bestLentolength. - Cut out the answer with
s.substring(bestStart, bestStart + bestLen). - Write
expandas a second method of the class, takings,leftandright. - Loop while the ends are valid and equal:
left >= 0,right < s.lengthands[left] === s[right]. The checks run left to right and stop at the first false one, so the characters are compared only when both ends are inside the string. - Move outward:
left--andright++. - Return
right - left - 1. The loop stops one step past the palindrome on both sides, so the palindrome runs fromleft + 1toright - 1, which is that many characters. If the first two characters already differ, the result is 0.
The solution in JavaScript
class Solution {
longestPalindrome(s) {
let bestStart = 0;
let bestLen = 0;
for (let i = 0; i < s.length; i++) {
const odd = this.expand(s, i, i);
const even = this.expand(s, i, i + 1);
const length = Math.max(odd, even);
if (length > bestLen) {
bestStart = i - Math.floor((length - 1) / 2);
bestLen = length;
}
}
return s.substring(bestStart, bestStart + bestLen);
}
expand(s, left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return right - left - 1;
}
}
JavaScript details worth knowing:
this.expand. Methods in a class don't see each other by bare name. InsidelongestPalindrome, the helper must be called asthis.expand(...).- Division is not integer division.
(length - 1) / 2is 1.5 whenlengthis 4, which is whyMath.flooris needed. Without it,bestStartwould be a fraction. - Reading past the end gives
undefined.s[right]withrightequal tos.lengthdoes not throw. The range checks come first anyway, so the comparison never depends on that. - Parameters are copies.
expandchanges its ownleftandright; the caller's variables are unaffected, because numbers are passed by value. s[i]indexes UTF-16 code units. That is fine for this lesson, whose strings contain only English letters and digits.
Complexity
Time: O(n²). There are 2n - 1 centers, and each expansion takes at most about n / 2 steps. A string like "aaaa…a" is the worst case, because every expansion runs to an end of the string.
Space: O(1) extra. Only a few numbers are kept. The returned substring is the only new string.
A table dp[i][j] that records whether s[i..j] is a palindrome gives the same time but costs O(n²) space. Manacher's algorithm finds the answer in O(n), but it goes beyond this lesson.
Edge cases and common mistakes
- Only odd centers. Skipping
this.expand(s, i, i + 1)misses palindromes like"bb". For"cbbd"the answer would be"c"instead of"bb". - Using
>=instead of>. A later palindrome of the same length would replace the first one. For"babad"the result would be"aba"instead of"bab". - Checking
s[left] === s[right]before the bounds. The bounds checks must come first in the condition. - Single characters.
"a"returns"a", and"ac"returns"a", the first of two palindromes of length 1. - Case matters.
"Aa"returns"A", because"A"and"a"are different characters. - A start that drifts for even palindromes. The formula
i - Math.floor((length - 1) / 2)works for both parities. For"cbbd"ati = 1the even palindrome has length 2 and starts at 1.
Testing
"babad"gives"bab"."cbbd"gives"bb"."abacdfgdcaba"gives"aba"."a"gives"a"."ac"gives"a"."Aa"gives"A"."aaaa"gives"aaaa"."forgeeksskeegfor"gives"geeksskeeg".
