Longest palindromic substring: expand from every center
Find the longest contiguous palindrome in a string by expanding around odd and even centers, with code and a precise complexity bound.
A palindromic substring is contiguous and reads the same in both directions. Expand outward from each character for odd lengths and each gap for even lengths, stopping when the ends differ. Keep the longest span found. This takes O(n²) time and O(1) extra space.
Choose a center in a word. Look one step left and right: if the letters match, the mirror grows. Also try the spaces between letters, because even-length mirrors have no middle letter.
A palindrome reads the same forward and backward. A substring must occupy one uninterrupted span of the input. In babad, bab and aba are both longest palindromic substrings of length three; returning either is correct. The problem is not to reorder letters or skip inconvenient ones.
Every palindrome has a center#
An odd-length palindrome such as racecar has one middle character. An even-length palindrome such as abba has a middle gap. Expand from both kinds of center while the characters on either side match. If they differ or a boundary is reached, no longer palindrome can have that center.
For a string of length n, there are n character centers and n−1 gaps, so there are 2n−1 centers to check. This is a useful completeness argument: every contiguous palindrome has exactly one of these centers.
Expand and record#
def longest_palindromic_substring(text: str) -> str:
best_start, best_end = 0, 0 # end is exclusive
def expand(left: int, right: int) -> tuple[int, int]:
while left >= 0 and right < len(text) and text[left] == text[right]:
left -= 1
right += 1
return left + 1, right
for center in range(len(text)):
for left, right in ((center, center), (center, center + 1)):
start, end = expand(left, right)
if end - start > best_end - best_start:
best_start, best_end = start, end
return text[best_start:best_end]The expansion function stops after moving one step beyond the valid palindrome, so it returns left + 1 and right as an exclusive end. The strict > comparison keeps the first longest answer when lengths tie. Empty input returns an empty string.
Boundaries and cost#
There are O(n) centers, and each expansion can walk O(n) characters on repetitive input such as aaaa…, giving O(n²) time. The algorithm stores only indices, so extra space is O(1) beyond the returned slice. Linear-time algorithms exist, but expand-around-center is usually the clearest choice when n² work is acceptable. Do not confuse this with longest common substring, which compares two strings rather than looking for symmetry inside one.
Longest common subsequence is a third question: it allows gaps and preserves order without requiring the selected characters to be adjacent.
Questions people also ask
2 QUESTIONSWhy do I need to check gaps between characters?
Even-length palindromes such as abba have their center between the two middle characters. Checking only characters would miss them.
Is this the same as longest palindromic subsequence?
No. A substring is contiguous. A subsequence may skip characters, so it can be longer and is solved with a different recurrence.