Problem overview
The method longestPalindrome receives a string s 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 first wins. Uppercase and lowercase letters are different characters, so "Aa" is not a palindrome.
For "babad" the answer is "bab". The substring "aba" is just as long, but it starts one position later. For "cbbd" the answer is "bb", a palindrome of even length. For "abacdfgdcaba" the answer is the first "aba", at the start of the string.
The statement asks for O(n²) time and O(1) extra space besides the returned string.
Approach: grow palindromes from their centers
The brute force checks every substring. There are about n²/2 of them and each check reads up to n characters, so it costs O(n³).
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 twice for an odd center, two neighbours for an even one. While both are inside the string and their characters are equal, move them one step outward. When they stop, the palindrome lies strictly between them and has right - left - 1 characters. Two matching ends on the outside of a palindrome make a longer palindrome, so the loop finds the longest one around that center.
The helper expand does this and returns the length. For "babad" it gives these lengths, for the odd center at each index and for the even center right after it:
| i | odd center (i, i) | even center (i, i + 1) |
|---|---|---|
| 0 | 1 | 0 |
| 1 | 3 | 0 |
| 2 | 3 | 0 |
| 3 | 1 | 0 |
| 4 | 1 | 0 |
The first 3 comes at i = 1 ("bab"), the second at i = 2 ("aba"). Because the centers go from left to right and a result replaces the best only when it is strictly longer, "bab" stays.
Step by step
- Create
bestStartandbestLen, both 0. The start and length are all that has to be remembered; the substring is cut out once at the end. - Loop over
iinrange(len(s)). Eachigives two centers: the characters[i]and the gap after it. - Call
self.expand(s, i, i)and store it inodd: the longest palindrome of odd length centered ons[i]. The lesson writes the helper last, so the loop stays short. - Call
self.expand(s, i, i + 1)and store it ineven. If the two characters differ, oriis the last index, the result is 0. - Take
length = max(odd, even), the longest palindrome of either kind aroundi. - Test
length > bestLen. The comparison is strict, so an equally long palindrome further right doesn't replace the first one. - Set
bestStarttoi - (length - 1) // 2, where this palindrome begins. An odd palindrome has(length - 1) / 2characters before its middles[i]. An even one haslength / 2 - 1characters before its left middles[i]. Both equal(length - 1) // 2. - Set
bestLentolength. This is the palindrome to beat from now on. - Return the slice
s[bestStart:bestStart + bestLen]. A slice leaves out its end index, so it takes exactlybestLencharacters. - Write the method
expandin the same class, takingself,s,leftandright. The calls above useself.expandfor that reason. - Write the
whilecondition:left >= 0andright < len(s)ands[left] == s[right]. - Move both ends outward inside the loop:
left -= 1andright += 1. - Return
right - left - 1. The loop stops one step beyond the palindrome on each side, so the palindrome runs fromleft + 1toright - 1.
The solution in Python
class Solution:
def longestPalindrome(self, s: str) -> str:
bestStart = 0
bestLen = 0
for i in range(len(s)):
odd = self.expand(s, i, i)
even = self.expand(s, i, i + 1)
length = max(odd, even)
if length > bestLen:
bestStart = i - (length - 1) // 2
bestLen = length
return s[bestStart:bestStart + bestLen]
def expand(self, s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
Python details worth a closer look:
- The condition's order protects the indexes.
andstops at the first false check, sos[left]ands[right]are read only when both are in range. Droppingleft >= 0would not raise an error for a negativeleft; Python would read from the end of the string. With the check removed,expand("aa", 0, 0)returns 3, becauses[-1]is the last"a". The correct answer is 1. //floors. It divides and rounds down to a whole number. Herelength - 1is never negative, so this is the same as dropping the fraction. Forlength = 4,(4 - 1) // 2is 1.- Slices don't raise errors.
s[bestStart:bestStart + bestLen]is safe even at the end of the string. - Strings are immutable. The solution never builds substrings while searching, only two numbers, which is why the extra space stays constant. The single substring is created by the final slice.
- A method calling another method.
expanddoesn't useselffor anything, but it is still called asself.expand(...), because it belongs to the class.
Complexity
Time: O(n²). There are 2n - 1 centers, and each expansion moves outward at most about n / 2 steps. A string of one repeated letter, like "aaaa", is the worst case, because every expansion runs until it reaches an end.
Space: O(1) extra. Only a handful of integers are kept, besides the returned string.
A table dp[i][j] that records whether s[i..j] is a palindrome works in the same time but needs O(n²) space. Manacher's algorithm reaches O(n) time, which goes beyond this lesson.
Edge cases and common mistakes
- Only odd centers. Without the
(i, i + 1)call,"cbbd"would return"b"instead of"bb". - Using
>=instead of>. A later palindrome of equal length would replace the earlier one, and"babad"would return"aba". - A wrong start index. Using
i - length // 2works for odd lengths but is off by one for even ones.i - (length - 1) // 2covers both. - Returning the length. The helper returns a length and the method returns a string. The cut happens once at the end.
- Single character and no repeats.
"a"returns"a"."ab"returns"a", the first of the two palindromes of length 1. - Case matters.
"Aa"returns"A", because"A"and"a"are different characters.
Testing
s = "babad"gives"bab".s = "cbbd"gives"bb".s = "abacdfgdcaba"gives"aba".s = "a"gives"a".s = "ab"gives"a".s = "Aa"gives"A".s = "racecar"gives"racecar".s = "aaaa"gives"aaaa".s = "forgeeksskeegfor"gives"geeksskeeg".
