Palindromes: Expand Around the Center
Reads the same both ways
"racecar" reads the same backwards. Checking one string is two indexes from the ends, stepping inward while the characters match:
def is_palindrome(s):
lo, hi = 0, len(s) - 1
while lo < hi: # compare the two ends, step both inward
if s[lo] != s[hi]:
return False
lo, hi = lo + 1, hi - 1
return True
It returned True for 'racecar' and False for 'abca'.
Longest Palindromic Substring asks for the longest piece of a string that reads the same both ways. Checking every substring that way is O(n³). A string of 1,000 characters has 500,500 substrings, and checking them all is up to 83,458,250 character comparisons.
Turn it around. A palindrome mirrors around its center, so instead of guessing the ends, pick the middle and grow outwards while the two ends match. There are two kinds of center. Odd-length palindromes like "racecar" have a middle character. Even-length ones like "abba" have no middle character: their center is the gap between the two b's. A string of n characters has n characters and n − 1 gaps: 2n − 1 centers.
Grow from each center
From a center, compare the two characters just outside the palindrome you have, and grow while they match. Every successful step is one more palindrome, and the first failure ends that center: nothing longer can be centered there, because its inner part would already have failed.
Try it below. Pick any center, a letter or a gap, and expand it a step at a time. The widget keeps every palindrome you've found and the longest. See how many centers it takes to find them all.
"abaxyzzyxf" has 14 palindromic substrings, and its longest, xyzzyx, is centered on a gap. Skip the gaps and you can never find it.
Each center expands at most n/2 times, so trying all 2n − 1 of them is O(n²) time, and it needs only two indexes: O(1) space.
Longest Palindromic Substring
Expand from every center, and keep the longest. The helper returns where the palindrome starts and how long it is. The loop runs one step past each end, so the palindrome is the part strictly between the final indexes:
Longest Palindromic Substring on "cbbd" — Green characters are the palindrome around the current center; an amber pair differs.
// how far a palindrome grows from the center between lo and hi; returns its first index and length
pair<int, int> expand(const string& s, int lo, int hi) {
while (lo >= 0 && hi < (int)s.size() && s[lo] == s[hi]) { lo--; hi++; }
return {lo + 1, hi - lo - 1}; // the loop stopped one step past each end
}
string longestPalindrome(const string& s) {
int start = 0, best = 0;
for (int i = 0; i < (int)s.size(); i++) {
for (auto [l, len] : {expand(s, i, i), expand(s, i, i + 1)}) { // centered on s[i], or on the gap after it
if (len > best) { start = l; best = len; }
}
}
return s.substr(start, best);
}
def expand(s, lo, hi):
"""How far a palindrome grows from the center between lo and hi: (first index, length)."""
while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
lo, hi = lo - 1, hi + 1
return lo + 1, hi - lo - 1 # the loop stopped one step past each end
def longest_palindrome(s):
start, best = 0, 0
for i in range(len(s)):
for l, length in (expand(s, i, i), expand(s, i, i + 1)): # centered on s[i], or on the gap after it
if length > best:
start, best = l, length
return s[start:start + best]
// how far a palindrome grows from the center between lo and hi: {first index, length}
static int[] expand(String s, int lo, int hi) {
while (lo >= 0 && hi < s.length() && s.charAt(lo) == s.charAt(hi)) { lo--; hi++; }
return new int[]{lo + 1, hi - lo - 1}; // the loop stopped one step past each end
}
static String longestPalindrome(String s) {
int start = 0, best = 0;
for (int i = 0; i < s.length(); i++) {
for (int[] p : new int[][]{expand(s, i, i), expand(s, i, i + 1)}) { // on s[i], or the gap after it
if (p[1] > best) { start = p[0]; best = p[1]; }
}
}
return s.substring(start, start + best);
}
// how far a palindrome grows from the center between lo and hi: [first index, length]
function expand(s, lo, hi) {
while (lo >= 0 && hi < s.length && s[lo] === s[hi]) { lo--; hi++; }
return [lo + 1, hi - lo - 1]; // the loop stopped one step past each end
}
function longestPalindrome(s) {
let start = 0, best = 0;
for (let i = 0; i < s.length; i++) {
for (const [l, len] of [expand(s, i, i), expand(s, i, i + 1)]) { // on s[i], or the gap after it
if (len > best) { start = l; best = len; }
}
}
return s.slice(start, start + best);
}
Each prints bab, bb, a, a, geeksskeeg and xyzzyx for "babad", "cbbd", "a", "ac", "forgeeksskeegfor" and "abaxyzzyxf". For "babad", "aba" is just as long as "bab"; the code keeps the first one it finds.
Counting them, and rearranging letters
Palindromic Substrings counts every palindromic substring, each place it appears counted separately. It's the same walk, adding one for every successful step:
def count_substrings(s):
count = 0
for center in range(2 * len(s) - 1): # 2n - 1 centers: even ones on a character, odd ones on a gap
lo, hi = center // 2, center // 2 + center % 2
while lo >= 0 and hi < len(s) and s[lo] == s[hi]:
count += 1 # every successful step is one more palindrome
lo, hi = lo - 1, hi + 1
return count
It returned 3, 6 and 14 for "abc", "aaa" and "abaxyzzyxf". In "aaa" the six are a, a, a, aa, aa and aaa.
Longest Palindrome sounds the same, but it isn't about substrings: you may rearrange the letters however you like. Then order doesn't matter, only counts. Every pair of a letter can mirror around the middle, and one leftover letter can sit in the middle itself:
def longest_palindrome_length(s):
counts = {}
for c in s:
counts[c] = counts.get(c, 0) + 1
length = sum(k - k % 2 for k in counts.values()) # every pair of a letter can mirror around the middle
has_odd = any(k % 2 for k in counts.values())
return length + (1 if has_odd else 0) # one letter may sit alone in the middle
It returned 7, 1 and 6 for "abccccdd", "a" and "aabbcc". "abccccdd" can become "dccaccd": two d's, four c's, and one a in the middle.
Faster ways exist. Manacher's algorithm reuses mirror information to find the longest palindrome in O(n), and a dynamic-programming table answers "is s[i..j] a palindrome?" for every pair in O(n²) time and space (Dynamic Programming). Expanding around centers is O(n²) with O(1) space, which is what interviews expect.
Spotting it
Clues:
- "palindromic substring", longest or how many: expand around the 2n − 1 centers;
- "is this a palindrome", one string: two indexes from the ends;
- "rearrange", "permutation of a palindrome": only the letter counts matter.
And the near-misses:
- a palindromic subsequence (letters may be skipped): expanding doesn't work; that's dynamic programming.
- almost a palindrome (delete at most one character): two indexes from the ends, trying both skips at the first mismatch (Valid Palindrome II, in Two Pointers).
- the shortest palindrome by adding characters in front: a prefix question, solved with KMP (Advanced String Algorithms).
Common mistakes
Only centering on characters.
Even-length palindromes have no middle character, so they're never found: "cbbd" returned c, where the answer is bb. Try the gaps too.
Slicing with the final indexes. s[lo:hi + 1] after the loop
The loop already stepped one past each end, so the slice takes a character too many, or reads from the end of the string when lo is −1: "abcd" gave 'abc' and "xabay" gave 'xab'. The palindrome is s[lo + 1:hi].
Counting distinct palindromes. A set of the substrings found
Palindromic Substrings counts every place a palindrome appears. With a set, "aaa" returned 3; the answer is 6.
Adding one for every odd count.
Only one letter can sit alone in the middle. Adding one per odd letter, "abccccdd" returned 8; the answer is 7.
Check yourself
Quiz
1 / 6Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Multiple choice
Practice problems
From easier to harder:
- Longest Palindrome: letters rearranged, so count pairs and allow one middle letter.
- Longest Palindromic Substring: expand around all 2n − 1 centers.
- Palindromic Substrings: the same walk, counting every successful step.
That's the Strings section. The Strings Quiz checks all three lessons.