Longest Palindromic Substring
You get a string s of lowercase English letters. Return its longest palindromic substring: the longest run of consecutive letters that reads the same forward and backward. If several substrings share that longest length, return the one that starts furthest to the left.
Function
- sstring
- the lowercase string to search
- Returnsstring
- the longest palindromic substring of s, the leftmost one when several tie
Constraints
1 ≤ s.length ≤ 2000sholds only lowercase English letters.- When several palindromes have the longest length, the answer is the one with the smallest start index.
Examples
- Input
- s = "bananas"
- Output
- "anana"
- Explanation
"anana"reads the same both ways and has 5 letters. Every longer piece fails at its ends:"banana"(b, a),"ananas"(a, s) and"bananas"(b, s).
- Input
- s = "xyzzyabba"
- Output
- "yzzy"
- Explanation
"yzzy"and"abba"are both palindromes of length 4, and nothing longer exists."yzzy"starts at index 1, before"abba"at index 5, so it wins the tie.
- Input
- s = "abcd"
- Output
- "a"
- Explanation
- No two letters are equal, so every palindrome is a single letter. The leftmost one is
"a".
Follow-up
Can you find the answer in O(n) time?
Hints
Open them one at a time. Each one gives away a little more.
Every palindrome mirrors around its middle. Look at
"aba"and"abba": where is the middle of each, and how many possible middles does a string of length n have?Stand at a middle. If the letters on both sides of it match, you have a palindrome two letters longer than before. When must you stop growing it, and why can nothing longer share that middle?
For each of the
2n-1middles (every letter and every gap between two neighbours), grow outward while the letters match and remember the longest result. Replace the best only when a new palindrome is strictly longer, so the leftmost one wins a tie.
Solution
A palindrome mirrors around its middle: a letter for odd length, like "anana", or the gap between two equal letters for even length, like "abba". Grow each palindrome outward from its middle and every comparison extends one you already found: O(n²) time and O(1) extra memory, against O(n³) for testing every substring on its own.
Check every substring
Correct, but does not finish on the largest tests
Intuition
Fix a start i and an end j, then compare letters inward from both ends until two differ or the pointers meet. Trying all n(n+1)/2 substrings cannot miss the answer. With starts going left to right, replacing the best only on a strictly longer palindrome keeps the leftmost.
Each test can walk half the substring. For 2000 copies of a, every substring is a palindrome: about n³/12 ≈ 6.7 × 10^8 letter comparisons.
Algorithm
- Start with the first letter as the best: start 0, length 1.
- For each start
iand each endj ≥ i, compare letters from both ends toward the middle until they differ or the pointers meet. - If no pair differed and
j-i+1beats the best length, recordiand that length. - Return the substring at the best start with the best length.
def longestPalindrome(s):
n = len(s)
best_start, best_len = 0, 1
for i in range(n):
for j in range(i, n):
# Compare s[i..j] from both ends toward the middle
left, right = i, j
while left < right and s[left] == s[right]:
left += 1
right -= 1
is_palindrome = left >= right
if is_palindrome and j - i + 1 > best_len:
best_start, best_len = i, j - i + 1
return s[best_start:best_start + best_len]Table of palindromes by length
Intuition
Testing "anana" compares a with a, then n with n, and that second comparison is the whole test of "nan". Store each answer instead: s[i..j] is a palindrome when its ends match and s[i+1..j-1] is one.
Fill a table pal[i][j] by length. Single letters are palindromes, two letters are when they match, and a longer cell reads the cell two letters shorter, already filled. In "bananas", pal[1][5] holds because s[1] and s[5] are both a and pal[2][4] ("nan") holds. Within a length the starts go left to right, so the first palindrome of a record length is the leftmost.
About n²/2 cells at O(1) each give O(n²) time. The cost is memory: 4 × 10^6 cells for n = 2000.
Algorithm
- Make an n × n table
pal, all false. - For each length from 1 to n, and each start
iwhose endj = i+length-1stays inside the string, compares[i]ands[j]. - Mark
pal[i][j]when they match and the length is at most 2 orpal[i+1][j-1]is true. - When a marked cell's length beats the best, record
iand the length. - Return the substring at the best start.
def longestPalindrome(s):
n = len(s)
# pal[i][j] is True when s[i..j] reads the same both ways
pal = [[False] * n for _ in range(n)]
best_start, best_len = 0, 1
for length in range(1, n + 1):
for i in range(n - length + 1):
j = i + length - 1
# Equal ends, and the part inside them is a palindrome (or too short to matter)
if s[i] == s[j] and (length <= 2 or pal[i + 1][j - 1]):
pal[i][j] = True
if length > best_len:
best_start, best_len = i, length
return s[best_start:best_start + best_len]Expand around every center
Intuition
A string of n letters has n letter centers and n-1 gap centers, so 2n-1 in all. From a center, step outward while the two letters match. The first mismatch, or the edge, ends the walk, and nothing longer can share that center, because it would contain the mismatched pair. One walk per center therefore finds that center's longest palindrome.
In "bananas", the walk from index 3 matches n with n and a with a, then stops at b and s: length 5, start 3 - (5-1)/2 = 1, so "anana". Two palindromes of equal length have the same parity, so the earlier center starts earlier. Walk the centers left to right and replace the best only on a strictly longer length.
The worst case is one repeated letter: about n²/2 = 2 × 10^6 steps for n = 2000, with a few integers of memory.
Algorithm
- Write
expand(left, right): while both indexes are inside the string and the letters match, moveleftdown andrightup. Returnright-left-1. - For each center from 0 to n-1, take the larger of
expand(center, center)andexpand(center, center+1). - If that length beats the best, set the best start to
center - (length-1)/2, rounded down, and the best length to it. - Return the substring at the best start with the best length.
def expand(s, left, right):
# Grow outward while the two ends match; return the palindrome's length
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
def longestPalindrome(s):
best_start, best_len = 0, 1
for center in range(len(s)):
# Odd lengths grow from one letter, even lengths from the gap after it
length = max(expand(s, center, center), expand(s, center, center + 1))
if length > best_len:
best_start = center - (length - 1) // 2
best_len = length
return s[best_start:best_start + best_len]
Pitfalls and edge cases
- Expanding only around letters misses every even palindrome:
"abba"returns"a". - The walk stops one step past each end, so the length is
right-left-1. Usingright-left+1counts two letters that do not match. - Replacing the best on an equal length returns the rightmost palindrome:
"abba"instead of"yzzy"for"xyzzyabba". - For a gap center,
center - length/2is one too far left. In"xyzzyabba"the gap after index 2 gives length 4 and start2 - (4-1)/2 = 1, not 0. - Filling the table by start from 0 upward reads
pal[i+1][j-1]before it is set. Fill by length, or walk the starts from the end.
Frequently asked questions3
What is the time complexity of Longest Palindromic Substring?
Expanding around centers takes O(n²) time and O(1) extra memory. The table of palindromes is also O(n²) time but stores n² cells, and checking every substring on its own is O(n³).
Should you use dynamic programming or expand around center?
Expand around center. Both take O(n²) time, but the table holds 4 × 10^6 cells for n = 2000 while expanding keeps a few integers. Expanding also stops at the first mismatch, so a string with few palindromes costs it far less than n² steps.
How is the longest palindromic substring different from the longest palindromic subsequence?
A substring is a run of consecutive letters, while a subsequence may skip letters. In "character" the longest palindromic substring is "ara", but "carac" is a palindromic subsequence of length 5. The subsequence version uses a table over (i, j) that drops one end when the two ends differ.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def longestPalindrome(s):
# Write code hereTest #1
Test #2
Test #3
Argument
s = "bananas"
Expected Output
"anana"