Problem overview
The function longest_palindrome 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 furthest to the left wins.
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 occurrence at the start. The string holds English letters and digits, and uppercase and lowercase are different characters, so "Aa" is not a palindrome.
The lesson asks for O(n²) time and O(1) extra space besides the returned string.
Approach: grow a palindrome from its middle
Checking every substring on its own 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, n characters and n - 1 gaps.
From a center, expand. Start two positions, left and right, on the same character (odd case) or on two neighbours (even case). While both are inside the string and the characters match, move them one step outward. When the loop stops, the palindrome sits strictly between the two positions, so it has right - left - 1 characters. A helper named expand does this and returns that length.
The main function calls expand twice for each index i: with (i, i) for the odd center and with (i, i + 1) for the even center. For "babad" the results 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
For "cbbd", the only index with a longer result is i=1, where odd=1 and even=2: the gap between the two b's is a center.
The program keeps only the best start and the best length. A palindrome of length characters centered at i starts at i - (length - 1) / 2, with integer division. For "babad" at i=1 with length 3 that is index 0, which gives "bab". For "cbbd" at i=1 with length 2 it is index 1, which gives "bb".
Step by step
- Take the bytes. Rust doesn't let you index a
Stringby position, sos.as_bytes()gives a slice of bytes that can be indexed. Letters and digits are one byte each, so comparing bytes compares characters. - Create
best_startandbest_len, both 0. The substring itself is cut out only once, at the end. - Loop over every
ifrom 0 up to the number of bytes, typed asi32. The positions arei32becauseexpandmovesleftbelow 0 when it passes the start, which ausizecan't hold. - Call
expand(bytes, i, i)for the longest odd palindrome aroundbytes[i]. - Call
expand(bytes, i, i + 1)for the longest even palindrome around the gap afteri. When the two characters differ, oriis the last index, the length is 0. - Take the larger of the two with
odd.max(even). - Compare with the best so far using a strict
>. A palindrome of equal length starts further right, and the first one must win. - Compute the start as
i - (length - 1) / 2. An odd palindrome has(length - 1) / 2characters before its middle, and an even one haslength / 2 - 1before its left middle character. Both equal(length - 1) / 2with integer division. - Record the length in
best_len. - Cut out the result after the loop: the slice of
sfrombest_starttobest_start + best_len, turned into a newStringwithto_string(). - Write
expandwith the bytes as&[u8]and twoi32parameters markedmut, returning ani32. - Loop while
left >= 0,rightis below the length, and the two bytes are equal, joined with&&. - Move both ends outward:
left -= 1andright += 1. - Return
right - left - 1. The loop stops one step past the palindrome on each side, so the palindrome runs fromleft + 1toright - 1.
The solution in Rust
impl Solution {
fn longest_palindrome(s: String) -> String {
let bytes = s.as_bytes();
let mut best_start = 0;
let mut best_len = 0;
for i in 0..bytes.len() as i32 {
let odd = Self::expand(bytes, i, i);
let even = Self::expand(bytes, i, i + 1);
let length = odd.max(even);
if length > best_len {
best_start = i - (length - 1) / 2;
best_len = length;
}
}
s[best_start as usize..(best_start + best_len) as usize].to_string()
}
fn expand(bytes: &[u8], mut left: i32, mut right: i32) -> i32 {
while left >= 0 && right < bytes.len() as i32 && bytes[left as usize] == bytes[right as usize] {
left -= 1;
right += 1;
}
right - left - 1
}
}
The Rust details worth a closer look:
- Casts and precedence. In
0..bytes.len() as i32, the cast binds tighter than the range operator, so it is the upper bound that becomes ani32. The loop variablei, and with itbest_startandbest_len, are theni32too. - Short-circuit order in the
while. The checksleft >= 0andright < bytes.len() as i32come first, and&&stops at the first one that fails. The bytes are indexed only when both positions are in range, soleft as usizenever sees a negative number. muton parameters.mut leftletsexpandchange its own copy. The caller'siis unchanged.- Slicing a
String.s[a..b]uses byte positions and needsusizebounds, hence the two casts. It works here because each character is one byte. A string with a character that takes several bytes, like"é"(2 bytes, 1 character), would panic if a cut fell inside it. to_string(). The slice is a&strborrowed froms. The function must return an ownedString, andto_string()copies the piece into one.Self::expand.expandtakes noself, so it is called by path, like a static method.
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 until it reaches an end.
Space: O(1) extra. Only a few integers are kept. The returned string is the only allocation, and it isn't counted as extra space. A table dp[i][j] that records whether s[i..j] is a palindrome gives the same time but takes O(n²) space, and Manacher's algorithm reaches O(n) time, which goes beyond this lesson.
Edge cases and common mistakes
- Forgetting even centers. With only
expand(i, i),"cbbd"would return"b"instead of"bb". - Using
>=instead of>. A later palindrome of the same length would replace the earlier one:"babad"would give"aba"instead of"bab". - A single character. For
"a"the odd expansion returns 1 and the even one returns 0, sincerightis already out of range. The answer is"a". - No repeated characters. For
"ab"every palindrome has length 1, and the first one,"a", stays. - Case matters. For
"Aa"the bytes differ, so the answer is"A". - Using
usizeforleft. When a palindrome reaches the start of the string,leftbecomes -1, which ausizecan't hold:left -= 1would overflow, panicking in a debug build and wrapping in an optimized one. - Off-by-one in the length. The loop stops after moving one step too far, so the length is
right - left - 1, notright - left.
Testing
"babad"gives"bab"."cbbd"gives"bb"."abacdfgdcaba"gives"aba"."a"gives"a"."ab"gives"a"."racecar"gives"racecar"."abba"gives"abba"."Aa"gives"A"."aacabdkacaa"gives"aca"."12321x"gives"12321".
