Longest Palindromic Substring

Introduction

A palindrome is a string that reads the same forward and backward, such as "racecar" or "madam". The longest palindromic substring (LPS) problem asks: given a string S of length n, find the longest contiguous substring of S that is a palindrome.

This problem has multiple algorithmic solutions ranging from O(n^3) brute force to O(n) using Manacher's algorithm. The expand-around-center approach provides a clean O(n^2) solution, while Manacher's algorithm achieves linear time by exploiting the symmetric structure of palindromes -- previously computed palindrome information is reused to avoid redundant character comparisons.

The LPS problem is fundamental in string processing and has applications in bioinformatics (finding palindromic DNA sequences), text analysis, and data compression.

Brute-Force Approach

The simplest approach checks every possible substring and tests whether it is a palindrome:

procedure LPSBruteForce(S): n = length(S) maxLen = 1 result = S[0] for i from 0 to n-1: for j from i+1 to n-1: if isPalindrome(S[i..j]) and (j - i + 1) > maxLen: maxLen = j - i + 1 result = S[i..j] return result

There are O(n^2) substrings, and checking each takes O(n), giving O(n^3) total time. This is impractical for strings longer than a few thousand characters.

Expand Around Center

A palindrome mirrors around its center. There are 2n - 1 possible centers: n single-character centers (for odd-length palindromes) and n - 1 between-character centers (for even-length palindromes). For each center, we expand outward while characters match.

procedure ExpandAroundCenter(S): n = length(S) start = 0, maxLen = 1 for center from 0 to n-1: // Odd-length palindromes left = center, right = center while left >= 0 and right < n and S[left] == S[right]: if right - left + 1 > maxLen: maxLen = right - left + 1 start = left left = left - 1 right = right + 1 // Even-length palindromes left = center, right = center + 1 while left >= 0 and right < n and S[left] == S[right]: if right - left + 1 > maxLen: maxLen = right - left + 1 start = left left = left - 1 right = right + 1 return S[start..start+maxLen-1]

Each expansion takes O(n) in the worst case, and there are O(n) centers, giving O(n^2) total time and O(1) extra space.

Manacher's Algorithm

Manacher's algorithm finds all maximal palindromic substrings in O(n) time. It transforms the string by inserting separator characters to handle both odd and even length palindromes uniformly, then uses previously computed results to skip redundant expansions.

Key Concepts

• Transformed string: Insert a special character (e.g., '#') between every pair of characters and at both ends. "abba" becomes "#a#b#b#a#". Every palindrome in the transformed string has odd length.
• P array: P[i] stores the radius of the longest palindrome centered at position i in the transformed string.
• Center and Right boundary: Maintain the center C and right boundary R of the rightmost palindrome found so far.

Algorithm

procedure Manacher(S): T = transform(S) // insert separators n = length(T) P = array of size n, all zeros C = 0, R = 0 for i from 0 to n-1: mirror = 2*C - i if i < R: P[i] = min(R - i, P[mirror]) // Attempt to expand palindrome centered at i while i + P[i] + 1 < n and i - P[i] - 1 >= 0 and T[i + P[i] + 1] == T[i - P[i] - 1]: P[i] = P[i] + 1 // Update center and right boundary if i + P[i] > R: C = i R = i + P[i] // Find maximum in P maxRadius = max(P) centerIndex = index of maxRadius in P start = (centerIndex - maxRadius) / 2 return S[start..start+maxRadius-1]

The key insight of Manacher's algorithm is that when position i falls within a known palindrome centered at C, the palindrome radius at i is at least the radius at its mirror position 2C-i, bounded by the distance to the right boundary R. This allows most positions to be resolved in O(1) time.

Worked Example

Find the longest palindromic substring of "babad" using expand-around-center:

Center 0 ('b'): "b" (length 1). No even expansion.

Center 1 ('a'): Expand: 'b' != 'b'? Actually S[0]='b', S[2]='b'. Match. "bab" (length 3). Further: out of bounds. Even: S[1]='a', S[2]='b'. No match.

Center 2 ('b'): Expand: S[1]='a', S[3]='a'. Match. "aba" (length 3). Further: S[0]='b', S[4]='d'. No match. Even: S[2]='b', S[3]='a'. No match.

Center 3 ('a'): "a" (length 1). Even: S[3]='a', S[4]='d'. No match.

Center 4 ('d'): "d" (length 1).

Result: "bab" or "aba" (both length 3).

Manacher's on "abacaba"

T = #a#b#a#c#a#b#a#P = [0,1,0,3,0,1,0,7,0,1,0,3,0,1,0]Maximum P[i] = 7 at position 7 (center 'c')Palindrome: "abacaba" (length 7)

Complexity Analysis

Manacher's O(n) bound is proved by observing that the right boundary R only moves to the right. Each expansion step advances R by one position, and R can advance at most 2n times total (the length of the transformed string). Combined with the O(1) operations when i < R, the total work is O(n).

Dynamic Programming Approach

Define dp[i][j] = true if S[i..j] is a palindrome. Then:

dp[i][j] = true if: S[i] == S[j] and (j - i <= 2 or dp[i+1][j-1])

Fill the table by increasing substring length. Track the longest palindrome found. This takes O(n^2) time and O(n^2) space, which is worse than expand-around-center on both counts but can be useful when all palindromic substrings need to be identified.

Implementation

def longest_palindrome(s): if len(s) < 2: return s start, max_len = 0, 1 def expand(left, right): nonlocal start, max_len while left >= 0 and right < len(s) and s[left] == s[right]: if right - left + 1 > max_len: start = left max_len = right - left + 1 left -= 1 right += 1 for i in range(len(s)): expand(i, i) # odd length expand(i, i + 1) # even length return s[start:start + max_len]def manacher(s): t = '#' + '#'.join(s) + '#' n = len(t) p = [0] * n c = r = 0 for i in range(n): mirror = 2 * c - i if i < r: p[i] = min(r - i, p[mirror]) while (i + p[i] + 1 < n and i - p[i] - 1 >= 0 and t[i + p[i] + 1] == t[i - p[i] - 1]): p[i] += 1 if i + p[i] > r: c, r = i, i + p[i] max_len = max(p) center = p.index(max_len) start = (center - max_len) // 2 return s[start:start + max_len]

Applications and Related Problems

• Bioinformatics: Palindromic DNA sequences are biologically significant; restriction enzymes cut DNA at palindromic recognition sites.
• Longest Palindromic Subsequence: Unlike substring (contiguous), this allows non-contiguous characters. Solved in O(n^2) by dynamic programming on the LCS of S and its reverse.
• Palindrome Partitioning: Partition a string into the minimum number of palindromic substrings. Solved in O(n^2) with DP.
• Count Palindromic Substrings: Count all palindromic substrings (not just the longest). Manacher's algorithm can be adapted for this.
• Eertree (Palindromic Tree): A data structure that stores all distinct palindromic substrings in O(n) space, supporting efficient palindrome queries.

References

• Manacher, G. "A New Linear-Time On-Line Algorithm for Finding the Smallest Initial Palindrome of a String." Journal of the ACM, vol. 22, no. 3, 1975, pp. 346-351.
• Gusfield, D. "Algorithms on Strings, Trees, and Sequences." Cambridge University Press, Chapter 9, 1997.
• Jeuring, J. "The Derivation of On-Line Algorithms, with an Application to Finding Palindromes." Algorithmica, vol. 11, 1994, pp. 146-184.
• Rubinchik, M. and Shur, A. M. "EERTREE: An Efficient Data Structure for Processing Palindromes in Strings." European Journal of Combinatorics, vol. 68, 2018, pp. 249-265.