Longest palindromic substring
In computer science, the longest palindromic substring problem requires identifying the longest contiguous sequence of characters within a given string that forms a palindrome, defined as a string that reads the same forwards and backwards.[1] For example, in the string "babad", the longest palindromic substrings include "bab" or "aba", both of length 3.[2] This problem is a classic challenge in string algorithms, fundamental to pattern recognition and text processing tasks.[3]
Efficient solutions to the problem leverage dynamic programming or specialized linear-time techniques. A standard dynamic programming approach constructs a two-dimensional table where each entry dp represents whether the substring from index i to j is palindromic, filling the table in O(1) time per entry to achieve an overall time complexity of O(n²) for a string of length n.[4] An alternative O(n²) method expands potential palindromes around each character or pair of characters as centers, checking for symmetry outward until mismatches occur.[1]
For optimal performance, Manacher's algorithm solves the problem in linear time, O(n), by preprocessing the string with sentinel characters to uniformly handle even- and odd-length palindromes, then computing palindrome radii around each position while skipping redundant expansions using a dynamic right boundary.[5] Originally introduced by Glenn Manacher in 1975 for related palindrome detection, this method has become the standard for linear-time computation and extends to applications in bioinformatics, such as analyzing DNA sequences for symmetric patterns.[6][3]
Background
Problem Definition
A palindrome is a string that reads the same forward and backward.[7] Examples include "racecar", which is symmetric around its center character 'c', and "aba", symmetric around 'b'.[8]
In computer science, a substring refers to a contiguous sequence of characters within a string, whereas a subsequence allows non-contiguous characters while preserving their relative order.[9][10] The longest palindromic substring problem specifically concerns contiguous palindromic sequences, distinguishing it from problems involving non-contiguous palindromic subsequences.[11]
Formally, given a string S of length n over some alphabet, the longest palindromic substring problem requires identifying the longest contiguous substring S[i..j] (using 0-based indexing, where i \leq j) such that S[i..j] is a palindrome.[12] The output may be the length j - i + 1 of this substring or the substring itself.[3]
Input specifications typically involve a single string S of length n, with constraints varying by context (e.g., 1 ≤ n ≤ 1000 in programming problems like LeetCode, or larger in theoretical analyses).[2] Edge cases include the empty string, which has no palindromic substring of positive length (length 0), and a single-character string, which is always a palindrome of length 1.[8]
Importance and Applications
The longest palindromic substring problem traces its roots to string algorithm research in the 1970s, with the seminal linear-time solution introduced by Glenn Manacher in 1975 for finding the smallest initial palindrome of a string, which laid the foundation for efficient detection of palindromic substrings. The algorithm presented in the paper was later adapted to find all palindromic substrings, including the longest one, in linear time.[6] This foundational work has influenced subsequent developments in efficient palindrome detection, establishing the problem as a cornerstone of theoretical computer science. Over time, the problem gained prominence in practical computing through its inclusion in programming contests and interview preparation platforms, notably as LeetCode problem 5 since the platform's early years around 2015.[2]
In bioinformatics, identifying the longest palindromic substring is crucial for analyzing DNA and RNA sequences, where palindromic regions often form stem-loop structures that regulate gene expression, replication, and transcription.[13] These sequences also serve as recognition sites for restriction enzymes, enabling precise cutting in recombinant DNA techniques and facilitating genome editing.[14] For instance, tools like palindrome finders scan nucleic acid data to locate such motifs, aiding in the prediction of functional elements like origins of replication or recombination hotspots.[13]
In natural language processing and linguistics, the problem supports tasks involving pattern recognition in text, such as detecting symmetric phrases for stylistic analysis in literature or identifying repeated structures in speech signals.[15] This can enhance applications like sentiment analysis by highlighting rhetorical devices or aid in text compression through palindrome-based encoding.[16] An illustrative example is the string "babad", where the longest palindromic substrings "bab" or "aba" demonstrate how such detection can reveal core symmetric elements in textual data, useful for summarization or anomaly detection in prose.[2]
Basic Algorithms
Brute Force Method
The brute force method for identifying the longest palindromic substring in a given string s of length n exhaustively examines every possible substring by generating all pairs of start and end indices, then verifies each candidate substring's palindromic property through direct character comparison. This naive approach prioritizes simplicity over efficiency, making it suitable for small inputs but impractical for longer strings due to its cubic time requirement.[17]
The algorithm proceeds in three main phases: substring generation, palindrome validation, and length tracking. First, nested loops create all substrings s[i..j] where $0 \leq i \leq j < n. For each such substring, a helper function checks palindromicity by initializing two pointers—one at the start (i) and one at the end (j)—and iteratively comparing characters while moving the pointers inward until they meet or a mismatch occurs. If the substring is a palindrome and its length (j - i + 1) exceeds the current maximum, the maximum length and corresponding substring indices are updated. This process ensures comprehensive coverage of all potential palindromes.[17]
The following pseudocode illustrates the implementation:
function longestPalindromicSubstring(s):
n = length(s)
maxLen = 1
start = 0
for i from 0 to n-1:
for j from i to n-1:
if isPalindrome(s, i, j) and (j - i + 1) > maxLen:
start = i
maxLen = j - i + 1
return substring(s, start, maxLen)
function isPalindrome(s, i, j):
while i < j:
if s[i] != s[j]:
return false
i += 1
j -= 1
return true
function longestPalindromicSubstring(s):
n = length(s)
maxLen = 1
start = 0
for i from 0 to n-1:
for j from i to n-1:
if isPalindrome(s, i, j) and (j - i + 1) > maxLen:
start = i
maxLen = j - i + 1
return substring(s, start, maxLen)
function isPalindrome(s, i, j):
while i < j:
if s[i] != s[j]:
return false
i += 1
j -= 1
return true
This runs in O(n^3) time, as there are O(n^2) substrings and each validation takes O(n) in the worst case.[17]
Consider the string s = "aba" as an illustrative walkthrough. The possible substrings are: "a" (indices 0-0, palindrome, length 1), "b" (1-1, palindrome, length 1), "a" (2-2, palindrome, length 1), "ab" (0-1, a ≠ b, not palindrome), "ba" (1-2, b ≠ a, not palindrome), and "aba" (0-2, a = a and center b matches, palindrome, length 3). The method identifies "aba" as the longest palindromic substring.[17]
The correctness of this method stems from its exhaustive enumeration: by inspecting every substring and accurately verifying palindromicity via end-to-end comparison, it guarantees discovery of the longest palindrome, assuming the input string contains at least one (which all non-empty strings do, via single characters).[17]
In terms of space complexity, the approach uses O(1) auxiliary space, relying solely on a constant number of variables for indices and length tracking, independent of input size.[17]
Dynamic Programming Approach
The dynamic programming approach employs a two-dimensional boolean array to systematically identify palindromic substrings by leveraging previously computed results for smaller substrings, thereby avoiding redundant verifications inherent in brute-force methods. This method constructs a table dp of size n \times n, where n is the length of the input string S, and dp[i][j] is true if the substring S[i \dots j] (using 0-based indexing) forms a palindrome.
The recurrence relation for filling the table is defined as follows:
dp =
\begin{cases}
(S = S) \land (j - i < 2 \lor dp[i+1][j-1]) & \text{if } i < j \\
\text{base case} & \text{otherwise}
\end{cases}
This checks if the characters at the boundaries match and, for substrings longer than two characters, if the inner substring is already a palindrome.
Base cases initialize the table for the smallest substrings: all single-character substrings are palindromes, so dp[i][i] = true for $0 \leq i < n; for length-two substrings, dp[i][i+1] = (S[i] == S[i+1]) for $0 \leq i < n-1. The table is filled in order of increasing substring length l from 3 to n: for each l, iterate over starting indices i from 0 to n - l, compute j = i + l - 1, apply the recurrence to set dp[i][j], and simultaneously track the longest palindrome by monitoring the maximum value of j - i + 1 where dp[i][j] is true, along with the corresponding starting index.
The following pseudocode illustrates the process:
function longestPalindromicSubstring(S):
n = length(S)
if n == 0: return ""
dp = 2D array of size n x n, initialized to false
max_len = 1
start = 0
// Base case: single characters
for i from 0 to n-1:
dp[i][i] = true
// Base case: length 2
for i from 0 to n-2:
if S[i] == S[i+1]:
dp[i][i+1] = true
max_len = 2
start = i
// Check substrings of length 3 to n
for len from 3 to n:
for i from 0 to n - len:
j = i + len - 1
if S[i] == S[j] and dp[i+1][j-1]:
dp[i][j] = true
if len > max_len:
max_len = len
start = i
return S[start : start + max_len]
function longestPalindromicSubstring(S):
n = length(S)
if n == 0: return ""
dp = 2D array of size n x n, initialized to false
max_len = 1
start = 0
// Base case: single characters
for i from 0 to n-1:
dp[i][i] = true
// Base case: length 2
for i from 0 to n-2:
if S[i] == S[i+1]:
dp[i][i+1] = true
max_len = 2
start = i
// Check substrings of length 3 to n
for len from 3 to n:
for i from 0 to n - len:
j = i + len - 1
if S[i] == S[j] and dp[i+1][j-1]:
dp[i][j] = true
if len > max_len:
max_len = len
start = i
return S[start : start + max_len]
This approach runs in O(n^2) time due to filling O(n^2) entries, each in constant time, and uses O(n^2) space for the table.
For the string S = "babad" (n=5), the table is filled as follows: all dp[i][i] are true; length 2 yields no palindromes, as all adjacent pairs differ (dp[0][1] "ba" false, dp[1][2] "ab" false, dp[2][3] "ba" false, dp[3][4] "ad" false). For length 3: dp[0][2] for "bab": S='b'==S[18]='b' and dp[19][19]=true, so true; dp[1][3] for "aba": S[19]='a'==S[20]='a' and dp[18][18]=true, so true; dp[2][4] for "bad": S[18]='b'!=S[21]='d', false. Length 4: all false (e.g., dp[0][3] "baba" b!=a, dp[1][4] "abad" a!=d). Length 5: "babad" b!=d false. Thus, the longest is length 3, e.g., "bab" at indices 0-2 or "aba" at 1-3.
The space complexity can be optimized to O(n) by using a one-dimensional array instead of the full 2D table, updating values in place row by row while only retaining the previous row's relevant entries, as longer substrings depend solely on the immediately preceding diagonal.
Advanced Algorithms
Expand Around Centers
The expand around centers algorithm provides an intuitive O(n²) time solution for finding the longest palindromic substring in a string of length n by treating every possible position as a potential center of a palindrome and expanding outward to verify symmetry. Every palindrome has a unique center: a single character for odd-length palindromes or the gap between two adjacent characters for even-length ones, leading to 2n - 1 possible centers to check. This approach leverages the symmetric nature of palindromes, comparing characters equidistant from the center until a mismatch occurs or the string boundaries are reached.
To implement the algorithm, iterate over each index i from 0 to n-1. For each i, first consider an odd-length palindrome centered at i by initializing left = i and right = i, then expand while left >= 0, right < n, and s[left] == s[right], decrementing left and incrementing right each time a match is found, updating the maximum length and corresponding substring if a longer palindrome is discovered. Next, consider an even-length palindrome centered between i and i+1 by initializing left = i and right = i+1, expanding similarly while the conditions hold. This process ensures all potential palindromes are examined without redundant checks beyond the expansions.
Here is pseudocode for the algorithm:
function longestPalindrome(s):
n = length(s)
start = 0
maxLength = 1
for i = 0 to n-1:
// Odd length centered at i
left = i
right = i
while left >= 0 and right < n and s[left] == s[right]:
if right - left + 1 > maxLength:
start = left
maxLength = right - left + 1
left -= 1
right += 1
// Even length centered between i and i+1
left = i
right = i + 1
while left >= 0 and right < n and s[left] == s[right]:
if right - left + 1 > maxLength:
start = left
maxLength = right - left + 1
left -= 1
right += 1
return substring(s, start, maxLength)
function longestPalindrome(s):
n = length(s)
start = 0
maxLength = 1
for i = 0 to n-1:
// Odd length centered at i
left = i
right = i
while left >= 0 and right < n and s[left] == s[right]:
if right - left + 1 > maxLength:
start = left
maxLength = right - left + 1
left -= 1
right += 1
// Even length centered between i and i+1
left = i
right = i + 1
while left >= 0 and right < n and s[left] == s[right]:
if right - left + 1 > maxLength:
start = left
maxLength = right - left + 1
left -= 1
right += 1
return substring(s, start, maxLength)
For example, consider the string "aabbaa". At index i=2 (character 'b'), the even-length expansion starts with left=2 ('b') and right=3 ('b'), which match; it then checks left=1 ('a') and right=4 ('a'), which match, identifying "abba" of length 4; further expansion to left=0 ('a') and right=5 ('a') confirms the full string as a palindrome of length 6. This demonstrates how expansions naturally discover longer palindromes when possible.
The algorithm's advantages include its straightforward implementation compared to dynamic programming approaches, which require an O(n²) space table, while this method uses only O(1) extra space beyond the input string. It avoids complex data structures or preprocessing, making it accessible for quick prototyping.
Its correctness stems from the exhaustive coverage of all 2n - 1 centers, ensuring that every possible palindromic substring—by definition centered at one of these positions—is detected during the expansions, with the global maximum tracked throughout.
Manacher's Algorithm
Manacher's algorithm, introduced by Glenn Manacher in 1975, computes the longest palindromic substring of a given string in linear time by efficiently determining the extent of all possible palindromes centered at each position. The algorithm achieves this by exploiting the symmetry of palindromes to avoid redundant character comparisons, building upon the expand-around-centers method but extending it to O(n) time through mirroring techniques.[5]
A key preprocessing step transforms the input string S of length n into an augmented string T of length $2n + 3 to uniformly handle both odd-length and even-length palindromes. This is done by inserting a special separator character, such as '#', between every pair of characters in S, and adding unique sentinels '^' at the beginning and '' at the end to prevent boundary issues during expansion. For example, for S = "aba", the transformed T = "^#a#b#a#". This setup ensures that every potential palindrome center in the original string aligns with a unique position in T, treating inter-character positions (for even palindromes) as explicit centers.[5]
The core data structure is an array P of the same length as T, where P represents the radius of the longest palindrome centered at position i in T; specifically, P is the largest integer such that the substring from i - P to i + P is a palindrome. The maximum value in P (excluding sentinels) determines the length of the longest palindromic substring in the original string, as the separators ensure P directly corresponds to the number of original characters in the palindrome.[5]
The algorithm proceeds in a single pass over T, maintaining two variables: C, the center of the rightmost palindrome boundary encountered so far (initially 0), and R, the right boundary of that palindrome (initially 0). For each position i = 1 to |T| - 2:
- If i < R, set P = \min(R - i, P[2 \cdot C - i]), using the known radius from the symmetric "mirror" position $2 \cdot C - i within the current palindrome to initialize the expansion.
- Otherwise, set P = 0.
- Then, expand the palindrome by incrementing P while T[i - P - 1] = T[i + P + 1].
- If i + P > R, update C = i and R = i + P.
This process tracks the maximum radius to identify the longest palindrome. The following pseudocode outlines the core loop after preprocessing and P initialization to zeros:
C = 0
R = 0
maxLen = 0
maxCenter = 0
for i = 1 to |T| - 2:
if i < R:
P[i] = min(R - i, P[2*C - i])
while T[i - (P[i] + 1)] == T[i + (P[i] + 1)]:
P[i] = P[i] + 1
if P[i] > maxLen:
maxLen = P[i]
maxCenter = i
if i + P[i] > R:
C = i
R = i + P[i]
C = 0
R = 0
maxLen = 0
maxCenter = 0
for i = 1 to |T| - 2:
if i < R:
P[i] = min(R - i, P[2*C - i])
while T[i - (P[i] + 1)] == T[i + (P[i] + 1)]:
P[i] = P[i] + 1
if P[i] > maxLen:
maxLen = P[i]
maxCenter = i
if i + P[i] > R:
C = i
R = i + P[i]
The longest palindromic substring can then be extracted from the original string using the center \maxCenter and length \maxLen.[5]
For the string "babad", the preprocessing yields T = "^#b#a#b#a#d#". Running the algorithm computes the P array, where the maximum value P = 3 $ occurs at centers corresponding to "bab" and "aba", confirming the longest palindromic substrings have length 3.[5]
The key innovation of Manacher's algorithm lies in leveraging the mirroring property of palindromes to reuse previously computed radii, ensuring that each character is compared at most a constant number of times across all expansions, thus achieving O(n) overall time complexity without redundant work.
Analysis and Optimizations
Time and Space Complexity
Asymptotic notation, such as big-O (O), provides an upper bound on the growth rate of an algorithm's time or space requirements as a function of the input size n, focusing on the dominant terms while ignoring constants and lower-order factors; for instance, O(n²) indicates quadratic growth, suitable for describing worst-case performance in string algorithms where n is the string length.[22]
The brute force method for finding the longest palindromic substring enumerates all possible O(n²) substrings and verifies each palindrome property through O(n) pairwise comparisons from the ends toward the center, yielding an overall time complexity of O(n³); it requires only O(1) auxiliary space beyond the input string, as no additional data structures are needed.[22]
The dynamic programming approach constructs a two-dimensional boolean table of size n × n to store whether each substring is palindromic, filling it via O(1) work per entry in a bottom-up manner over O(n²) entries, resulting in O(n²) time complexity; the initial space complexity is O(n²) for the table, but it can be optimized to O(n) space by retaining only the current and previous rows during computation, since dependencies are limited to adjacent diagonals.[22][23]
The expand around centers technique treats each of the 2n + 1 possible centers (characters and gaps between them) as a potential palindrome midpoint and expands outward by comparing characters symmetrically until a mismatch, performing up to O(n) comparisons per center in the worst case, for a total time complexity of O(n²); it uses O(1) auxiliary space, relying solely on indices without extra storage.[22]
Manacher's algorithm preprocesses the string by inserting special characters to handle even- and odd-length palindromes uniformly, then computes a radius array in a single pass, achieving O(n) time complexity and O(n) space for the transformed string and radius array.[6] The linear time arises from amortizing expansions to constant time per position: the algorithm maintains a current right boundary of the largest known palindrome centered at some position, and for each new position i within this boundary, the radius is mirrored from its symmetric counterpart, avoiding redundant comparisons; expansions only proceed beyond the boundary when necessary, and each mismatch updates the boundary without overlap, ensuring the total character comparisons across all positions sum to at most 2n, as every index is visited once and extensions are charged to boundary advances.[6]
The following table summarizes the time and space complexities of these algorithms, highlighting trade-offs in efficiency for practical implementations:
| Algorithm | Time Complexity | Space Complexity | Notes |
|---|
| Brute Force | O(n³) | O(1) | Inefficient for long strings but straightforward to implement. |
| Dynamic Programming | O(n²) | O(n²) or O(n) | Space-optimizable; useful when O(n) time is unnecessary. |
| Expand Around Centers | O(n²) | O(1) | Optimal space for quadratic time; intuitive for coding interviews. |
| Manacher's Algorithm | O(n) | O(n) | Linear time ideal for large inputs; requires careful preprocessing. |
Special Cases and Edge Handling
All algorithms for finding the longest palindromic substring must handle the empty string input gracefully, typically by performing an initial length check (n=0) and returning an empty substring or a length of 0, preventing unnecessary computations.[24][25] In the dynamic programming approach, the table initialization skips the loop entirely for n=0. The expand-around-centers method similarly avoids iteration over centers. Manacher's algorithm preprocesses the string with sentinels but initializes boundaries (L=0, R=-1) to yield zero-length results for empty inputs.[26]
Single-character strings represent the simplest non-empty case, where the entire string is a palindrome of length 1, which all methods identify immediately without expansion or table filling.[24] Brute force and expand-around-centers detect this in the base case of their loops. Dynamic programming sets diagonal entries (dp = true) to confirm it. Manacher's treats each position as an odd-length center with initial radius 0, expandable only if adjacent characters match, but for n=1, it returns the character directly.[25]
When the input consists of all identical characters, such as "aaa", the longest palindromic substring is the entire string, and algorithms efficiently recognize this pattern. The dynamic programming table fills entirely with true values due to matching adjacent pairs. In expand-around-centers, expansions from any center reach the string bounds. Manacher's algorithm leverages its symmetry mirroring, setting palindrome radii (P) to cover prefixes and the full length, achieving this in linear time without redundant checks.[27][26]
Distinguishing between even- and odd-length palindromes is crucial, as the former center between characters while the latter center on them; the expand-around-centers method addresses this by iterating over 2n-1 potential centers, treating odd lengths with a single index offset (j=0) and even with adjacent pairs (j=1).[24] Manacher's algorithm unifies handling through preprocessing: inserting a special separator (e.g., '#') between characters and sentinels at ends transforms the string to treat even and odd cases uniformly as odd-length palindromes in the modified array.[26] Dynamic programming and brute force handle both via length-based iterations without special distinction.
For long strings containing many overlapping palindromes, recursive implementations of checking or expanding may risk stack overflow due to deep call stacks, though standard iterative versions of all algorithms (brute force loops, DP table filling, center expansions, and Manacher's linear pass) avoid this issue entirely.[28] Developers are advised to prefer iterative approaches for robustness on inputs exceeding typical recursion limits, such as strings longer than 10^4 characters.[25]
Algorithms treat strings as sequences of abstract symbols, so they handle Unicode or non-ASCII characters seamlessly as long as the programming language supports Unicode strings (e.g., via UTF-8 encoding), comparing code points or graphemes equivalently to ASCII without modification.[24]
To enhance efficiency in practice, particularly for expand-around-centers and brute force, implementations can incorporate early stopping during expansions: halt outward checks if the current palindrome length exceeds the remaining string segments from the center, as further expansion cannot yield a longer result. All algorithms are adaptable to such bounds-aware optimizations, reducing constant factors without altering asymptotic complexity.[24][26]