Problem overview
The method longestPalindrome(s: String): String returns the longest palindromic substring of s. A palindrome reads the same forward and backward, such as "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 first, furthest to the left, wins. Uppercase and lowercase letters are different characters, so "Aa" is not a palindrome.
For "babad" the answer is "bab". The substring "aba" has the same length, but "bab" starts earlier. For "cbbd" the answer is "bb", an even-length palindrome. For "abacdfgdcaba" the answer is "aba", the copy at the start.
Approach: grow a palindrome from its middle
Checking every substring separately costs O(n³): about n²/2 substrings, each up to n characters long. Looking at palindromes from the middle is cheaper. Every palindrome has a center: its middle character when its 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, which are n characters and n - 1 gaps.
From a center, expand. Start with two positions left and right, either 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 and has right - left - 1 characters. It is the longest palindrome around that center.
The loop visits every index i and expands two centers: (i, i) for odd lengths and (i, i + 1) for even lengths. For "babad" the lengths found are:
i=0 odd=1 even=0
i=1 odd=3 even=0
i=2 odd=3 even=0
i=3 odd=1 even=0
i=4 odd=1 even=0
The center at index 1 gives the first palindrome of length 3, "bab". The center at index 2 gives another of length 3, "aba", but it is not longer, so it does not replace the first. For "cbbd" the only even palindrome is at i = 1, where even is 2.
The method remembers only the best start and the best length, and cuts out the substring once at the end.
Step by step
- Create
bestStartandbestLenasvars, both 0. They record where the best palindrome so far starts and how long it is. - Loop over every position with
i <- 0 until s.length. Eachibrings two centers, the characters(i)and the gap after it. - Call
expand(s, i, i)and keep the result inodd: the longest palindrome whose middle iss(i). The lesson writes the helper at the end and assumes it exists for now. - Call
expand(s, i, i + 1)and keep the result ineven. If the two characters differ, oriis the last index, it is 0. - Take
math.max(odd, even)aslength, the longest palindrome centered atiof either kind. - Compare
length > bestLen. The comparison is strict, so a palindrome just as long as the best one, which starts further right, never replaces it. - Set
bestStarttoi - (length - 1) / 2. An odd palindrome has(length - 1) / 2characters before its middles(i). An even one haslength / 2 - 1before its left middle character, which is the same number once the division rounds down. - Set
bestLentolength. - Return
s.substring(bestStart, bestStart + bestLen)as the last expression.substringleaves out its end index, so it takes exactlybestLencharacters. - Write
expandas a method of the same class, withs,leftandrightas parameters and anIntresult. - Copy the parameters into
varslandr. Scala parameters cannot be reassigned. - Loop while
l >= 0 && r < s.length && s(l) == s(r). The first two tests keep both ends inside the string, and&&stops at the first false one, so characters are compared only when both indexes are valid. - Move outward:
l -= 1andr += 1. - Return
r - l - 1. The loop stops one step past the palindrome on each side, so it runs froml + 1tor - 1.
The solution in Scala
class Solution {
def longestPalindrome(s: String): String = {
var bestStart = 0
var bestLen = 0
for (i <- 0 until s.length) {
val odd = expand(s, i, i)
val even = expand(s, i, i + 1)
val length = math.max(odd, even)
if (length > bestLen) {
bestStart = i - (length - 1) / 2
bestLen = length
}
}
s.substring(bestStart, bestStart + bestLen)
}
def expand(s: String, left: Int, right: Int): Int = {
var l = left
var r = right
while (l >= 0 && r < s.length && s(l) == s(r)) {
l -= 1
r += 1
}
r - l - 1
}
}
The Scala details worth a closer look:
- Strings are indexed with parentheses.
s(l)gives aChar, and==on twoChars compares their values. - Parameters are values.
leftandrightcannot be changed, which is whyexpandcopies them. The copies get shorter names,landr, because they are separate variables from the parameters. - Integer division truncates.
(length - 1) / 2drops the remainder. Sincelengthis at least 1 whenever it is used, the numerator is never negative, so truncating is the same as rounding down. - Methods can call each other in any order.
longestPalindromecallsexpand, which is defined below it in the class, by its plain name.
Complexity
Time: O(n²). There are 2n - 1 centers, and each expansion takes at most about n / 2 steps. A string of one repeated letter is the worst case.
Space: O(1) extra, besides the returned string. The method keeps a handful of integers.
A table that tells whether each substring is a palindrome gives the same time with O(n²) space. Manacher's algorithm finds the answer in O(n) but goes beyond this lesson.
Edge cases and common mistakes
- A single character.
"a"gives"a". Its odd expansion has length 1, and the even expansion starts out of range and returns 0. - No repeated characters.
"ab"gives"a", and"ac"gives"a": every palindrome has length 1, and the first one wins. - Case matters.
"Aa"gives"A". - Only odd centers. A version that expands only
(i, i)returns"c"for"cbbd"and misses"bb". >=instead of>. The later palindrome would replace an equally long earlier one, and"babad"would give"aba"instead of"bab".- Wrong start for even palindromes. The formula
i - (length - 1) / 2works for both kinds because the division rounds down. A formula such asi - length / 2fits odd lengths but starts one position too far left for even ones. - Off-by-one in the length. The expansion stops one step too far on both sides, which is why the length is
r - l - 1and notr - l + 1. - A whole-string palindrome.
"abba"and"racecar"are returned whole.
Testing
"babad"gives"bab"."cbbd"gives"bb"."abacdfgdcaba"gives"aba"."a"gives"a"."ab"gives"a"."Aa"gives"A"."racecar"gives"racecar"."forgeeksskeegfor"gives"geeksskeeg"."12321x"gives"12321".
