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" and "ace" is not. When several palindromes share the greatest length, the one that starts furthest to the left wins.
For "babad" the answer is "bab". The string "aba" is just as long, but "bab" starts first. For "cbbd" the answer is "bb", an even-length palindrome. For "abacdfgdcaba" the answer is "aba", which appears at the start and at the end, and the first one is returned. Letters are case-sensitive: "Aa" is not a palindrome, so its answer is "A".
The statement asks for O(n²) time and O(1) extra space besides the returned string.
Approach: grow a palindrome from its middle
Checking every substring separately costs O(n³): there are about n²/2 substrings and each takes up to n steps 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 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. A helper called expand does exactly this and returns the length.
For each index i the solution calls expand(chars, i, i) for the odd center on a character and expand(chars, i, i + 1) for the even center on the gap after it. In "babad", expand from index 1 on the character gives 3 (the palindrome "aba"), and from index 2 it also gives 3 ("bab"). For "cbbd" the odd expansion at index 1 gives 1 and the even one gives 2, the "bb".
The solution remembers only the start and the length of the best palindrome so far. It replaces them only for a strictly longer one. Centers are visited from left to right, so among equally long palindromes the first one stays.
Step by step
- Copy the characters into an array. A Swift
Stringcan't be indexed with an integer, but an[Character]can. - Create
bestStartandbestLen, both 0, withvar. The substring itself is cut out once, at the end. - Loop
iover0..<chars.count. Eachigives two centers: the character and the gap after it. - Call
expand(chars, i, i)and store it inodd. The helper is written last. - Call
expand(chars, i, i + 1)and store it ineven. If the two characters differ, oriis the last index, the result is 0. - Take
max(odd, even)aslength, the longest palindrome centered ati. - Compare with
length > bestLen. The test is strict so that the leftmost of equal palindromes is kept. - Compute the start as
i - (length - 1) / 2. An odd palindrome has(length - 1) / 2characters before its middle. An even one haslength / 2 - 1before its left middle, which is the same number after integer division. - Store the new
bestLen. - Return the substring:
chars[bestStart..<bestStart + bestLen]turned back into aString. - Write
expandas a method of the same class. It takes the character array and two integers, all without argument labels, and returns anInt. - Copy the parameters into variables of the same names, because Swift parameters can't be changed.
- Loop while both ends are in range and the characters match. The range checks come first, so
chars[left]andchars[right]are only read when both indexes are valid. - Move the ends outward with
left -= 1andright += 1. - Return
right - left - 1. The loop stops one step past the palindrome on both sides, so it spansleft + 1toright - 1.
The solution in Swift
class Solution {
func longestPalindrome(_ s: String) -> String {
let chars = Array(s)
var bestStart = 0
var bestLen = 0
for i in 0..<chars.count {
let odd = expand(chars, i, i)
let even = expand(chars, i, i + 1)
let length = max(odd, even)
if length > bestLen {
bestStart = i - (length - 1) / 2
bestLen = length
}
}
return String(chars[bestStart..<bestStart + bestLen])
}
func expand(_ chars: [Character], _ left: Int, _ right: Int) -> Int {
var left = left
var right = right
while left >= 0 && right < chars.count && chars[left] == chars[right] {
left -= 1
right += 1
}
return right - left - 1
}
}
The Swift details worth a closer look:
- Shadowing parameters.
var left = leftdeclares a new local variable that hides the parameter of the same name. From that line on,leftis the mutable copy. Without it,left -= 1would not compile, because function parameters are constants. - Slicing back to a string.
chars[a..<b]is anArraySlice<Character>. Passing it toString(...)builds aStringfrom the characters. - Unlabeled parameters. The
_before each name means callers writeexpand(chars, i, i)with no labels. InsidelongestPalindromethe call is by name alone because both methods belong to the same class. - Short-circuit order.
&&stops at the firstfalse. Readingchars[left]before checkingleft >= 0would trap at run time whenleftreaches-1, and the program would crash. - Integer division.
/on twoIntvalues truncates toward zero. Herelength - 1is never negative, so it rounds down. - No
++or--. Swift has no increment operators, so the code uses+= 1and-= 1.
Complexity
Time: O(n²). There are 2n - 1 centers, and each expansion takes at most about n / 2 steps. The final slice costs O(n).
Space: O(1) extra, if you don't count the character array and the returned string. Beyond those, only a handful of integers are kept. A table dp[i][j] telling whether s[i..j] is a palindrome works in the same time but needs O(n²) space.
Edge cases and common mistakes
- Only odd centers. Without the call on
(i, i + 1),"cbbd"would return"b"instead of"bb". - Wrong start for even palindromes. The start formula uses
(length - 1) / 2for both kinds. For"abba"the even center at index 1 gives length 4 and start 1 - 1 = 0, so the answer is"abba". - Ties. The comparison
length > bestLenmust be strict. With>=,"babad"would return"aba". - Single characters.
"a"returns"a"and"ab"returns"a", because every single character is a palindrome of length 1. - Case.
"Aa"returns"A": uppercase and lowercase letters differ. - Checking the range after the characters. Swapping the conditions in the
whilewould index outside the array.
Testing
"babad"gives"bab"."cbbd"gives"bb"."abacdfgdcaba"gives"aba"."a"gives"a", and"ab"gives"a"."abba"gives"abba", and"racecar"gives"racecar"."Aa"gives"A"."aacabdkacaa"gives"aca"."forgeeksskeegfor"gives"geeksskeeg".
