vault

Palindromic Substrings

19 min read

Palindromic Substrings

A palindrome is a string that reads the same forward and backward ("racecar", "abba", "a", the empty string). Two LeetCode problems live in the palindromic-substring family: LC 647 (Count Palindromic Substrings) asks for the number of palindromic substrings in s, counting duplicates by position; LC 5 (Longest Palindromic Substring) asks for the longest one. A third — LC 132 (Palindrome Partitioning II) — asks for the minimum number of cuts to partition s into palindromic pieces, and uses the LC 647 DP table as its sub-routine. Three solution techniques exist in increasing sophistication: (1) DP with dp[i][j] indicating “is s[i..j] a palindrome?” — O(n²) time and space; (2) expand around each center — O(n²) time, O(1) space, slightly faster constant factor; (3) Manacher’s Algorithm — O(n) time. Each has a place: DP is the most general (gives the full table needed for downstream problems like LC 132); expand-around-center is the cleanest interview answer for LC 5; Manacher is the asymptotic optimum but an engineering exercise to write correctly.

1. Intuition — Three Different Lenses on the Same Problem

A palindrome has two characterizations and two algorithmic strategies emerge from them.

Recursive characterization. s[i..j] is a palindrome if and only if (a) s[i] == s[j] and (b) s[i+1..j-1] is a palindrome. The base cases are i == j (single character — always palindrome) and i + 1 == j (two characters — palindrome iff equal). This bottom-up characterization gives the DP: fill dp[i][j] for short substrings first, then longer ones.

Center-out characterization. Every palindrome has a center. For odd-length palindromes the center is a single character; for even-length palindromes the center is a position between two characters. So there are exactly 2n − 1 possible centers in a string of length n. From each center, expand outward as long as the symmetric pair of characters is equal; this enumerates every palindrome containing that center. Total cost: each expansion runs in O(n), summed over 2n − 1 centers, gives O(n²).

Pre-computed-arms characterization (Manacher). Computing the maximum palindrome arm at every position can be done in O(n) total by reusing earlier arms within an active palindrome’s reflection. This is Manacher’s Algorithm; we summarize its core idea in §6 and link out for the full treatment.

The recognition signal in interview problems: anything with the word “palindrome” + a substring-bounded question (longest, count, partition into) should trigger the DP / expand-around-center reflex. The pure O(n²) solutions are usually accepted by LeetCode; reach for Manacher only if the constraint demands it (n up to 10^5 or higher with tight time limits).

The historical note: the O(n²) DP is folklore from the 1960s. The center-expansion technique is widely attributed to interview-preparation literature without a single primary citation. Manacher’s paper (1975) is the canonical linear-time algorithm; Gusfield (1997) presents it in textbook form using a Z-function-like approach.

2. Tiny Worked Example — Filling the DP Table

Let s = "aaba" (length n = 4). We want every palindromic substring.

By eye: single characters "a", "a", "b", "a" (4 palindromes); two-character "aa" (1 palindrome at indices [0,1]); three-character — check "aab" (no), "aba" (yes, indices [1,3]); four-character "aaba" (no — s[0] = 'a' == s[3] = 'a', but middle "ab" is not a palindrome). Total: 4 + 1 + 1 = 6 palindromic substrings.

State: dp[i][j] = True iff s[i..j] (inclusive) is a palindrome, defined for 0 ≤ i ≤ j ≤ n − 1.

Recurrence:

dp[i][j] = True                              if i == j                       (single char)
        = (s[i] == s[j])                     if i + 1 == j                  (two chars)
        = (s[i] == s[j]) AND dp[i+1][j-1]    otherwise

Iteration order. The recurrence reads dp[i+1][j-1] — a cell of strictly smaller “length” j − i − 2. So we must fill the table in increasing order of substring length, the same length-outer signature used by Matrix Chain Multiplication and Burst Balloons.

Length 1 (i == j): all True.

j=0j=1j=2j=3
i=0T
i=1T
i=2T
i=3T

Length 2 (j = i + 1):

  • dp[0][1]: s[0]='a', s[1]='a', equal. T.
  • dp[1][2]: 'a' vs 'b', unequal. F.
  • dp[2][3]: 'b' vs 'a', unequal. F.
j=0j=1j=2j=3
i=0TT
i=1TF
i=2TF
i=3T

Length 3:

  • dp[0][2] (“aab”): s[0]='a' vs s[2]='b', unequal. F.
  • dp[1][3] (“aba”): s[1]='a' vs s[3]='a', equal; dp[2][2] = T. T.
j=0j=1j=2j=3
i=0TTF
i=1TFT
i=2TF
i=3T

Length 4:

  • dp[0][3] (“aaba”): s[0]='a' vs s[3]='a', equal; dp[1][2] = F. So F.
j=0j=1j=2j=3
i=0TTFF
i=1TFT
i=2TF
i=3T

Counting True cells: 4 + 1 + 0 + 1 + 0 + 0 = 6. ✓ (Counting the upper triangle including the diagonal.)

Longest palindrome: scan for the largest j − i + 1 such that dp[i][j] = T. Both "aa" (length 2) and "aba" (length 3) qualify; "aba" is longer at length 3, so the answer to LC 5 on "aaba" is "aba".

3. Pseudocode

3.1 DP — Boolean Table

fill_palindrome_table(s):
    n := length(s)
    dp := 2D array of size n × n, init False
    for i := 0 to n - 1:
        dp[i][i] := True                            # length 1
    for i := 0 to n - 2:
        dp[i][i+1] := (s[i] == s[i+1])              # length 2
    for length := 3 to n:                           # length-outer
        for i := 0 to n - length:
            j := i + length - 1
            dp[i][j] := (s[i] == s[j]) AND dp[i+1][j-1]
    return dp

count_palindromic_substrings(s):
    dp := fill_palindrome_table(s)
    return number of (i, j) with dp[i][j] = True

longest_palindromic_substring(s):
    dp := fill_palindrome_table(s)
    best_i, best_j := 0, 0
    for i := 0 to n - 1:
        for j := i to n - 1:
            if dp[i][j] AND (j - i) > (best_j - best_i):
                best_i, best_j := i, j
    return s[best_i .. best_j]

3.2 Expand Around Center

expand(s, left, right):
    while left >= 0 AND right < length(s) AND s[left] == s[right]:
        left -= 1
        right += 1
    return (left + 1, right - 1)                    # the last valid (l, r) is one-step-back

count_palindromic_substrings(s):
    n := length(s)
    count := 0
    for center := 0 to 2n - 2:                      # 2n-1 centers
        left := center / 2
        right := left + (center % 2)                # odd: same; even: next
        l, r := left, right
        while l >= 0 AND r < n AND s[l] == s[r]:
            count += 1
            l -= 1
            r += 1
    return count

The center indexing trick: center ranges over 0, 1, ..., 2n - 2. For even center, both left and right start at center / 2 (single-character center, odd-length palindrome). For odd center, left = center / 2 and right = left + 1 (two-character center, even-length palindrome). Every palindrome of s is counted exactly once because every palindrome has exactly one center.

4. Python Implementation

4.1 DP — O(n²) Time, O(n²) Space

def count_palindromic_substrings_dp(s: str) -> int:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    count = 0
    # length 1
    for i in range(n):
        dp[i][i] = True
        count += 1
    # length 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            count += 1
    # length >= 3
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                count += 1
    return count
 
 
def longest_palindromic_substring_dp(s: str) -> str:
    n = len(s)
    if n == 0:
        return ""
    dp = [[False] * n for _ in range(n)]
    best_i, best_len = 0, 1
    for i in range(n):
        dp[i][i] = True
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            if best_len < 2:
                best_i, best_len = i, 2
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                if length > best_len:
                    best_i, best_len = i, length
    return s[best_i: best_i + best_len]

4.2 Expand Around Center — O(n²) Time, O(1) Space

def count_palindromic_substrings_expand(s: str) -> int:
    def expand(left: int, right: int) -> int:
        cnt = 0
        while left >= 0 and right < len(s) and s[left] == s[right]:
            cnt += 1
            left -= 1
            right += 1
        return cnt
 
    total = 0
    for i in range(len(s)):
        total += expand(i, i)        # odd-length palindromes centered at i
        total += expand(i, i + 1)    # even-length palindromes centered between i and i+1
    return total
 
 
def longest_palindromic_substring_expand(s: str) -> str:
    if not s:
        return ""
 
    def expand(left: int, right: int) -> tuple[int, int]:
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1                  # last valid
 
    best = (0, 0)
    for i in range(len(s)):
        l1, r1 = expand(i, i)
        if r1 - l1 > best[1] - best[0]:
            best = (l1, r1)
        l2, r2 = expand(i, i + 1)
        if r2 - l2 > best[1] - best[0]:
            best = (l2, r2)
    return s[best[0]: best[1] + 1]

The expand-around-center version is usually preferred in interview settings: it is shorter, has O(1) extra space, and runs faster in practice due to better cache behavior (no large 2D table to allocate).

4.3 Manacher — O(n) Time

The full implementation belongs in Manacher’s Algorithm; we sketch only the interface here. Manacher returns an array p such that p[i] is the radius of the longest palindrome centered at position i of the transformed string (interleaved with sentinel characters to unify odd / even cases). From p you can recover both the count and the longest palindrome in O(n) post-processing.

5. Complexity

ApproachTimeSpaceNotes
DP boolean tableO(n²)O(n²)Provides the dp[i][j] table needed by LC 132 and similar downstream problems
Expand around centerO(n²)O(1)Best constant factor for LC 5 / 647 in practice
Manacher’s AlgorithmO(n)O(n)Asymptotically optimal; fiddly to implement

Why all three are O(n²) or O(n) boils down to the number of palindromic substrings: in the worst case (s = "aaa...a" of length n), there are Θ(n²) palindromic substrings (every substring is a palindrome). LC 647 must enumerate them, so its lower bound is Ω(n²). LC 5 (longest only) does not have this lower bound — it can be solved in O(n) via Manacher because reporting just one extreme does not require enumerating all.

Count is Θ(n²) in value but computable in O(n) time

Manacher computes, for each of the 2n − 1 centers of the transformed string, the radius p[i] of the longest palindrome there. The number of palindromes centered at i is ⌈p[i] / 2⌉ (equivalently (p[i] + 1) // 2 on the standard #-interleaved transform), so the LC 647 answer is Σ_i (p[i]+1)//2 — a single O(n) summation over the radius array, no extra space beyond the array. The value of that sum can be Θ(n²) (for s = "aaa…a" of length n it is n(n+1)/2, since every substring is a palindrome), but a Θ(n²)-valued count is not the same as a Θ(n²)-time algorithm — the integer fits in O(1) space. This was verified by direct trace: on "aaa", "abba", "racecar", and "aaba" the Manacher sum agrees with both the DP and expand-around-center counts (6, 6, 10, 6 respectively). The amortized linearity of Manacher itself is confirmed by the standard argument that the active palindrome’s right boundary Center + Radius is non-decreasing and Center strictly increases each outer iteration (Wikipedia: Longest palindromic substring).

6. The Three Approaches Side-by-Side

6.1 DP

Pros: Produces the full n × n Boolean table, which is exactly the input some downstream problems need (LC 132 minimum cuts, LC 516 longest palindromic subsequence if reused with a related recurrence, etc.). Easy to teach: bottom-up filling matches the recursive characterization 1-to-1.

Cons: O(n²) space. For n = 10^5 this is 10^10 bits — too much.

When to use: Whenever a downstream computation needs to query “is s[i..j] a palindrome?” in O(1). The DP table is the right precomputation.

6.2 Expand Around Center

Pros: O(1) space (no DP table). Cleanest LC 5 / 647 implementation. Tight constant factor.

Cons: Cannot answer “is s[i..j] a palindrome?” in O(1) — to query an arbitrary substring, you would re-scan it. So this approach does not substitute for the DP when palindromicity is queried as a sub-routine.

When to use: LC 5 and LC 647 directly.

6.3 Manacher

Pros: O(n) time — the asymptotic optimum.

Cons: Subtle to implement correctly. Sentinel-character interleaving is a common bug source. Most coding-interview settings accept O(n²) solutions for n ≤ 1000; Manacher’s payoff appears only when n ≥ 10^4-ish.

When to use: Hard problems with tight time limits and n ≥ 10^4. Otherwise, expand-around-center suffices.

7. Connection to LC 132 (Palindrome Partitioning II — Min Cuts)

LC 132 asks: partition s into palindromic substrings using the minimum number of cuts. Approach in two phases:

Phase 1. Compute the boolean palindrome table dp[i][j] using the DP from §4.1 — O(n²) time and space.

Phase 2. Compute cuts[i] = minimum cuts to partition s[0..i]. Recurrence:

cuts[i] = 0                                              if dp[0][i]
        = min over j in [1, i] of cuts[j-1] + 1          if dp[j][i]
                                                          (only j with palindromic suffix considered)

The first clause says: if the entire prefix is already a palindrome, no cuts needed. Otherwise, find a palindromic suffix s[j..i] and pay 1 cut plus the optimal cuts for s[0..j-1]. Take the minimum over all valid j.

def min_cut_palindrome(s: str) -> int:
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = True
    for i in range(n - 1):
        dp[i][i + 1] = (s[i] == s[i + 1])
    for length in range(3, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
 
    cuts = [0] * n
    for i in range(n):
        if dp[0][i]:
            cuts[i] = 0
            continue
        cuts[i] = i                                       # worst case: cut between every char
        for j in range(1, i + 1):
            if dp[j][i]:
                cuts[i] = min(cuts[i], cuts[j - 1] + 1)
    return cuts[n - 1]

Total O(n²) time. The Phase-1 DP table is reused inside Phase 2 — this is why the Boolean DP table is the right sub-routine for the LC 132 family even though expand-around-center is faster for the standalone LC 647.

8.1 Longest Palindromic Subsequence (LC 516)

Subsequence, not substring — characters need not be contiguous. Different DP: dp[i][j] = length of LPS of s[i..j]. Recurrence:

dp[i][j] = dp[i+1][j-1] + 2                  if s[i] == s[j]
        = max(dp[i+1][j], dp[i][j-1])        otherwise

Same O(n²) complexity but unrelated to palindromic substrings — confusing the two is a common interview slip. A famous identity: LPS(s) = LCS(s, reverse(s)) — see Longest Common Subsequence.

8.2 Shortest Palindromic Superstring

Given s, find the shortest palindrome containing s as a prefix (or as a substring). Reduces to: find the longest palindromic prefix of s; append the reverse of the rest. Solvable in O(n) with Knuth-Morris-Pratt failure function tricks or Manacher.

8.3 Number of Distinct Palindromic Substrings

LC 647 counts palindromic substrings with multiplicity (each (i, j) pair). The distinct-string version (count distinct palindromes by their content) is harder; the optimal O(n) algorithm uses the eertree / palindromic tree (Rubinchik & Shur 2015), out of scope for typical interviews.

8.4 Palindrome Pairs

Given a list of words, find all pairs (i, j) such that words[i] + words[j] is a palindrome. LC 336. Reduces to a clever Trie + reversal trick; not a substring DP problem despite the palindromicity.

8.5 K-Palindrome (Approximate)

s is a k-palindrome if it can be turned into a palindrome by changing at most k characters. DP variant of LC 5 with an extra dimension for the change budget; also relates to Edit Distance between s and reverse(s).

9. Diagram — DP Table Dependencies

flowchart LR
    BR["dp[i+1][j-1]<br/>shorter inner substring"] --> C["dp[i][j]<br/>= s[i]==s[j] AND inner"]
    EQ["s[i] == s[j]<br/>character endpoints"] --> C

What this diagram shows. Computing dp[i][j] requires two pieces: (a) dp[i+1][j-1], the inner substring being a palindrome — a cell of length j − i − 1, strictly shorter than the cell we’re filling; (b) the character equality s[i] == s[j] at the endpoints. The dependency on a shorter inner cell forces the length-outer iteration order (or alternatively, bottom-up by i from n-1 down + left-to-right by j, which also satisfies the read-before-write order). Filling the table row-by-row top-down does not — dp[0][j] would depend on dp[1][j-1], which is on a later row. This is the same iteration-order trap as Matrix Chain Multiplication and Burst Balloons; the cure is the same length-outer signature.

10. Common Interview Problems

ProblemLeetCode #Approach
Palindromic Substrings (count)LC 647Expand-around-center (O(1) space) or DP
Longest Palindromic SubstringLC 5Expand-around-center; Manacher for tight constraints
Palindrome Partitioning II (min cuts)LC 132DP table + 1D cuts DP
Palindrome Partitioning I (all partitions)LC 131Backtracking with palindrome check (DP precompute helps)
Longest Palindromic SubsequenceLC 516Different DP recurrence (subsequence ≠ substring)
Valid PalindromeLC 125O(n) two-pointer, no DP needed
Shortest PalindromeLC 214KMP / Manacher trick on s + '#' + reverse(s)
Palindrome PairsLC 336Trie + reversed-prefix matching
Number of Distinct Palindromic SubsequencesLC 730Hard 2D DP with character-bound dimensions
Construct K Palindrome StringsLC 1400Counting parity trick (not DP)

The dp[i][j] palindrome table is a reusable sub-routine — many palindrome problems compose it with downstream logic (cuts, partitions, scoring).

11. Pitfalls

11.1 Wrong Iteration Order

The DP recurrence reads dp[i+1][j-1]. If you fill row-by-row top-down (for i in range(n): for j in range(n): ...), you read dp[i+1][...] from a row that has not yet been filled. The cell holds False (or whatever default), and your DP misses many palindromes. Length-outer is the canonical fix; alternatively, iterate i from n-1 down to 0 and j from i upward — this also satisfies the read-before-write order because dp[i+1][...] (lower row) is filled before dp[i][...].

11.2 Off-by-One in Length-2 Base Case

dp[i][i+1] (length 2) does not recurse to dp[i+1][i-1] — that would be a malformed cell. Treat length 2 as a base case checked separately (dp[i][i+1] = (s[i] == s[i+1])). Skipping this and letting the recurrence compute it produces a False for any matched pair like "aa".

11.3 Confusing Substring with Subsequence

Substring is contiguous; subsequence is not. LC 5 / 647 ask about substrings; LC 516 asks about subsequences. The DP recurrences are different. Mixing them is a top-3 interview slip-up. The recurrence shape gives the giveaway: substring DP advances i+1 and j-1 together (closes both ends); subsequence DP can advance just one (drop one end).

11.4 Even-Length Palindromes in Expand-Around-Center

Forgetting the even-length case (start with left = i, right = i + 1) misses every palindrome of even length — "abba", "aa", etc. This bug has no syntax error and silently undercounts by ~half on average inputs. Always run expand(i, i) and expand(i, i+1).

11.5 Off-by-One in Center Indexing

The clever 2n - 1 centers enumeration via for center in range(2*n - 1) with left = center // 2, right = left + (center % 2) is correct but easy to misderive. If you write 2*n (one too many) or shift the parity wrong, you double-count or miss cases. Prefer the explicit two-loop version (one for odd centers, one for even) unless code golf is a priority.

11.6 String Slicing Cost in Expand-Around-Center

Don’t return s[left:right+1] from expand and compare lengths via len(...) — string slicing is O(n) per call. Return the indices and pick the longest after the fact; only slice the final result.

11.7 Unicode / Multibyte Characters

For Unicode input, s[i] may not be a single user-perceived character (combining marks, surrogate pairs). LeetCode’s typical inputs are ASCII, so this rarely matters in interviews — but a real palindrome checker over arbitrary text needs grapheme-cluster awareness.

11.8 Mismatched DP Cell Initialization

Initializing dp with [[False] * n for _ in range(n)] is correct in Python; [[False] * n] * n is wrong — it creates n references to the same row, and writes to dp[0][·] propagate to every “row.” This is a Python-specific aliasing trap.

11.9 Manacher Sentinel Choice

If you implement Manacher, the sentinel character (typically '#') must not appear in the input — otherwise the transformation breaks. Use a control character or assert the input is a known alphabet. A subtler bug: the sentinel should also be placed before the first and after the last character to handle boundaries uniformly.

11.10 LC 132 Min Cuts: Off-By-One in cuts[j-1] + 1

The recurrence cuts[i] = min(cuts[j - 1] + 1) for valid j requires j ≥ 1 (so j - 1 ≥ 0). If j == 0 and dp[0][i] = True, the answer is 0 cuts (the entire prefix is a palindrome) — handled by the explicit if dp[0][i]: cuts[i] = 0 branch before the loop. Forgetting this branch produces cuts[n-1] ≥ 1 for inputs like "aba" whose answer is 0.

11.11 Counting “Distinct” vs “Occurrences”

LC 647 counts occurrences ("aaa" has 3 single-char palindromes, 2 length-2 palindromes, 1 length-3 palindrome — total 6). LC 730 (“Count Different Palindromic Subsequences”) counts distinct strings. Misreading “distinct” causes wrong answers; it is also a much harder problem.

11.12 Large Outputs

For s = "a" * n with n = 1000, the count of palindromic substrings is n(n+1)/2 = 500500. Fits in 32-bit, but for n = 10^5 it is ≈ 5 × 10^9 — overflows 32-bit signed. Use 64-bit / Python int.

12. Open Questions

  • Why does O(n) Manacher work — what is the amortization argument? The total expansion work across all centers is bounded by O(n) because each expansion step advances the right boundary of the “active palindrome,” and once advanced it never retreats. Detailed in Manacher’s Algorithm.
  • Is there a sub-O(n²) algorithm for LC 132 (min palindrome cuts)? O(n²) is standard; some specialized structures achieve O(n²) with smaller constants but not asymptotic improvement (Hirschberg-style space optimization gives O(n) space for the cuts answer alone).
  • Does the eertree / palindromic tree generalize to weighted palindromes? Active research area in stringology; not interview-relevant.

13. See Also

Graph View

Backlinks