Problem overview
The method longestPalindrome receives a string s and returns its longest palindromic substring. A palindrome reads the same forward and backward, and a substring is a run of consecutive characters. When several palindromes share the greatest length, the one that starts first, furthest to the left, is returned. Upper and lower case 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", an even-length palindrome. For "abacdfgdcaba" it is "aba", the copy at the start.
The statement asks for O(n²) time and O(1) extra space besides the returned string.
Approach: grow palindromes from their centers
Checking every substring on its own costs O(n³): about n²/2 substrings, each up to n characters to check. A better view starts from the middle. 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, on the center (the same character, or two neighbours), and move them one step outward while both are inside the string and the characters match. When they stop, the palindrome lies strictly between them, so it has right - left - 1 characters. That is the longest palindrome around that center.
The helper expand does this and returns the length. For each index i the solution calls it twice: expand(s, i, i) for the odd center on s[i], and expand(s, i, i + 1) for the even center between s[i] and s[i + 1]. For "babad" the results are:
i odd even
0 1 0
1 3 0
2 3 0
3 1 0
4 1 0
For "cbbd", the only even palindrome is at i = 1, where expand("cbbd", 1, 2) returns 2, the length of "bb".
Where does the palindrome start?
Knowing only the length and the center i, the start is i - Math.floor((length - 1) / 2). An odd palindrome has (length - 1) / 2 characters before its middle s[i]. An even one has length / 2 - 1 characters before s[i], which is its left middle. Both equal Math.floor((length - 1) / 2). In "cbbd" with i = 1 and length 2, the start is 1 - 0 = 1, so the substring from index 1 is "bb".
Why the first one wins
The centers are visited from left to right, and the best result is replaced only by a strictly longer palindrome. A later palindrome of the same length starts further right, so it never replaces the first. That gives the tie-break the statement asks for.
Step by step
- Declare
bestStartandbestLenwithlet, both 0. Remembering where the best palindrome starts and how long it is is enough; the substring is cut out once at the end. - Loop
iover every index ofs. Each index gives two centers, the character and the gap after it. - Call
this.expand(s, i, i)and store it inodd. The helper is written last. Assuming it exists keeps the loop short. - Call
this.expand(s, i, i + 1)and store it ineven. If the two characters differ, oriis the last index, the result is 0. - Take
Math.max(odd, even)aslength, the longest palindrome of either kind aroundi. - Test
length > bestLen, strictly, to keep the leftmost palindrome on ties. - Set
bestStarttoi - Math.floor((length - 1) / 2). - Set
bestLentolength. - Return
s.substring(bestStart, bestStart + bestLen).substringleaves out its end index, so this takes exactlybestLencharacters. - Write
expandas a method of the class, belowlongestPalindrome. It takes the string and the two ends and returns a number. That is why the calls above writethis.expand. - Loop while
left >= 0,right < s.lengthands[left] === s[right]. The range checks come first, so the characters are compared only when both ends are inside the string. - Move outward with
left--andright++: the two characters matched, so the palindrome grows by one on each side. - Return
right - left - 1. The loop stops one step past the palindrome on both sides, so the palindrome runs fromleft + 1toright - 1.
The solution in TypeScript
class Solution {
longestPalindrome(s: string): string {
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: string, left: number, right: number): number {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return right - left - 1;
}
}
Some TypeScript details:
this.expand. Inside a method,expandis reached throughthis. Writing a bareexpand(...)would look for a variable of that name, not a method of the class.- Parameters can be reassigned.
expandchangesleftandrightdirectly. Numbers are passed by value, so the caller's variables are unaffected. - Division gives a fraction.
(length - 1) / 2is 1 whenlengthis 3 but 0.5 when it is 2, becausenumberis a double.Math.floorturns it into a whole number, which an index needs. - Out-of-range reads don't throw.
"abc"[5]isundefined, not an error. The bound checks in thewhilecondition matter anyway: without them,undefined === undefinedwould betruewhen both ends run off the string, and the loop would never stop. s[left] === s[right]compares two one-character strings by value, and the comparison is case-sensitive.
Complexity
Time: O(n²). There are 2n - 1 centers, and each expansion moves at most about n / 2 steps in each direction.
Space: O(1) extra. Only a few numbers are kept, besides the substring that is returned. A table dp[i][j] that records whether s[i..j] is a palindrome gives the same time with O(n²) space. Manacher's algorithm reaches O(n), but it goes beyond this lesson.
Edge cases and common mistakes
- One character.
"a"returns"a". The odd expansion returns 1 and the even one returns 0. - No repeats.
"ab"returns"a", and"abcd"returns"a": every palindrome has length 1, and the first one wins. - The whole string.
"aaaa"returns"aaaa", found from the even center between the two middle characters. - Case matters.
"Aa"returns"A", since"A"and"a"are different characters. - Only checking odd centers. This finds
"b"in"cbbd"instead of"bb". - Using
>=in the comparison. A later palindrome of the same length would replace the first, so"babad"would return"aba". - Swapping the loop checks. Reading
s[left]before checkingleft >= 0would reads[-1], which isundefined. The result may be right by luck, but the order says what you mean. - Returning the length. The method returns the substring, not its length.
Testing
"babad"gives"bab"."cbbd"gives"bb"."abacdfgdcaba"gives"aba"."a"gives"a"."ab"gives"a"."aaaa"gives"aaaa"."Aa"gives"A"."forgeeksskeegfor"gives"geeksskeeg".
