Palindrome DP

Palindromes, strings that read the same forward and backward, are a favorite topic in algorithm interviews, and for good reason. Their symmetric structure creates overlapping subproblems everywhere. Checking whether one substring is a palindrome often depends on whether a smaller substring inside it is also a palindrome. That recursive overlap is exactly where dynamic programming thrives.

There are several distinct palindrome problems, and they require different techniques. The key is knowing which tool fits which variant.

Longest palindromic substring: expand around center

LeetCode 5 presents the most common palindrome problem: find the longest substring (contiguous characters) that forms a palindrome. The most intuitive approach is expand around center: pick a center position, then extend outward as long as both sides match.

A palindrome can be centered on a single character (odd length, like "aba") or on the gap between two characters (even length, like "abba"). So for a string of length n, there are 2n - 1 possible centers. For each center, expanding takes $O(n)$ time in the worst case, giving $O(n^2)$ overall with $O(1)$ space, with no table needed.

def longestPalindrome(s):
    start, max_len = 0, 1

    def expand(l, r):
        while l >= 0 and r < len(s) and s[l] == s[r]:
            l -= 1
            r += 1
        return l + 1, r - l - 1  # start index, length

    for i in range(len(s)):
        # Odd-length palindromes
        s1, l1 = expand(i, i)
        if l1 > max_len:
            start, max_len = s1, l1
        # Even-length palindromes
        s2, l2 = expand(i, i + 1)
        if l2 > max_len:
            start, max_len = s2, l2

    return s[start:start + max_len]

This is clean and fast in practice. But there is also a DP formulation.

Longest palindromic substring: the DP approach

Define dp[i][j] as a boolean: is s[i..j] a palindrome? The recurrence is straightforward. A single character is always a palindrome: dp[i][i] = True. Two adjacent characters form a palindrome if they match: dp[i][i+1] = (s[i] == s[i+1]). For longer substrings: dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1].

You must iterate by increasing substring length, because dp[i][j] depends on dp[i+1][j-1], a shorter substring that starts one position later and ends one position earlier.

def longestPalindromeDP(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start, max_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
            start, max_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 > max_len:
                    start, max_len = i, length

    return s[start:start + max_len]

This is $O(n^2)$ time and $O(n^2)$ space. For the substring problem specifically, expand-around-center is usually preferred since it uses $O(1)$ space. But the DP table becomes essential when you need to answer many palindrome queries, for instance, in palindrome partitioning problems where you need to quickly check whether any substring is a palindrome.

Longest palindromic subsequence

LeetCode 516 changes the problem: find the longest subsequence (not necessarily contiguous) that forms a palindrome. Given "bbbab", the answer is 4: the subsequence "bbbb".

This is where expand-around-center breaks down completely. A subsequence can skip characters, so there is no "center" to expand around. You must use DP.

Define dp[i][j] as the length of the longest palindromic subsequence in s[i..j]. The recurrence splits into two cases. If the endpoints match (s[i] == s[j]), those two characters can bookend a palindrome built from the interior: dp[i][j] = dp[i+1][j-1] + 2. If the endpoints do not match, at least one must be excluded: dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

Base case: every single character is a palindromic subsequence of length 1, so dp[i][i] = 1.

Walking through an example

Consider s = "bbbab". We build the table for increasing substring lengths.

Length 1: All dp[i][i] = 1. The diagonal is all 1s.

Length 2: dp[0][1]: s[0]='b', s[1]='b', they match, so dp[0][1] = dp[1][0] + 2 = 0 + 2 = 2. Similarly dp[2][3]: 'b' vs 'a', no match, so max(dp[3][3], dp[2][2]) = 1. And dp[3][4]: 'a' vs 'b', no match, so 1. But dp[1][2]: 'b' vs 'b', match, so 2.

Length 3: dp[0][2]: s[0]='b', s[2]='b', match, so dp[1][1] + 2 = 3. dp[1][3]: 'b' vs 'a', no match, so max(dp[2][3], dp[1][2]) = max(1, 2) = 2. dp[2][4]: 'b' vs 'b', match, so dp[3][3] + 2 = 3.

Length 4: dp[0][3]: 'b' vs 'a', no match, so max(dp[1][3], dp[0][2]) = max(2, 3) = 3. dp[1][4]: 'b' vs 'b', match, so dp[2][3] + 2 = 1 + 2 = 3.

Length 5: dp[0][4]: 'b' vs 'b', match, so dp[1][3] + 2 = 2 + 2 = 4.

The answer is dp[0][4] = 4, corresponding to "bbbb".

Iteration order

The dependency structure dictates iteration order. Since dp[i][j] depends on dp[i+1][j-1], dp[i+1][j], and dp[i][j-1], you need cells below and to the left to already be filled. There are two natural ways to achieve this.

By increasing length: Iterate substring lengths from 1 to n. For each length, sweep the starting index. This is the most common approach.

def longestPalinSubseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for gap in range(1, n):
        for i in range(n - gap):
            j = i + gap
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

From bottom-right: Iterate i from n-1 down to 0, and for each i, iterate j from i+1 up to n-1. When you process dp[i][j], row i+1 is already complete, and dp[i][j-1] was computed earlier in the current row.

def longestPalinSubseq(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

Both approaches are $O(n^2)$ time and $O(n^2)$ space.

Space optimization

Since each row i only depends on row i+1, you can reduce space to $O(n)$ by keeping only one row and updating it in place. The trick is that when computing the new dp[i][j], you need the old dp[i+1][j-1], but that cell may have been overwritten. You save it in a temporary variable before it gets clobbered.

def longestPalinSubseqOpt(s):
    n = len(s)
    dp = [1] * n
    for i in range(n - 2, -1, -1):
        prev = 0
        for j in range(i + 1, n):
            temp = dp[j]
            if s[i] == s[j]:
                dp[j] = prev + 2
            else:
                dp[j] = max(dp[j], dp[j - 1])
            prev = temp
    return dp[n - 1]

Here prev holds the value of dp[i+1][j-1], what dp[j-1] was before the current row's updates overwrote it. This brings space down to $O(n)$ while keeping $O(n^2)$ time.

Palindrome partitioning: minimum cuts

LeetCode 132 introduces a different flavor of palindrome DP: given a string, partition it into the fewest pieces such that every piece is a palindrome. For "aab", the answer is 1 cut: "aa" | "b".

This requires two layers of DP. First, precompute a table is_pal[i][j] that tells you whether s[i..j] is a palindrome, using the same recurrence from the substring problem. Second, define cuts[i] as the minimum number of cuts needed for s[0..i].

For each position i, try every possible last palindrome ending at i. If s[j..i] is a palindrome, then cuts[i] = min(cuts[i], cuts[j-1] + 1). If the entire prefix s[0..i] is a palindrome, then cuts[i] = 0.

def minCut(s):
    n = len(s)
    # Precompute palindrome table
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            if s[i] == s[j] and (j - i <= 2 or is_pal[i + 1][j - 1]):
                is_pal[i][j] = True

    cuts = list(range(n))  # worst case: cut before every char
    for i in range(n):
        if is_pal[0][i]:
            cuts[i] = 0
            continue
        for j in range(1, i + 1):
            if is_pal[j][i]:
                cuts[i] = min(cuts[i], cuts[j - 1] + 1)
    return cuts[n - 1]

The palindrome precomputation is $O(n^2)$, and the cut DP is also $O(n^2)$, so the total is $O(n^2)$ time and space.

Manacher's algorithm

For completeness: there exists an $O(n)$ algorithm for finding all palindromic substrings. Manacher's algorithm uses previously computed palindrome radii to skip redundant comparisons, exploiting the mirror property of palindromes. If you know a long palindrome centered at position c with radius r, then positions within that palindrome have mirror counterparts, and their palindrome radii carry over (with some boundary adjustments).

Manacher's is rarely required in interviews, but it is good to know it exists. For a detailed walkthrough, see cp-algorithms: Manacher's Algorithm. When a problem seems to need $O(n^2)$ palindrome checking and the constraints are tight ($n$ up to $10^6$ or $10^7$), Manacher's is the tool that brings it down to $O(n)$.

The key idea: transform the string by inserting separators (e.g. "abc" becomes "#a#b#c#") so that all palindromes become odd-length, eliminating the even/odd case split. Maintain a "rightmost palindrome" boundary [c, r]. For each center i, initialize its radius using the mirror dp[2*c - i], then expand. When expansion extends past r, update c and r.

def manacher(s):
    # Transform: "abc" -> "#a#b#c#"
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n  # p[i] = radius of palindrome centered at i in t
    c = r = 0    # center and right boundary of rightmost palindrome

    for i in range(n):
        mirror = 2 * c - i
        if i < r:
            p[i] = min(r - i, p[mirror])
        # Expand around center 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] += 1
        # Update rightmost palindrome
        if i + p[i] > r:
            c, r = i, i + p[i]

    # Find the longest palindrome in the original string
    max_len, center = max((p[i], i) for i in range(n))
    start = (center - max_len) // 2  # map back to original string index
    return s[start:start + max_len]

p[i] gives the radius of the palindrome centered at position i in the transformed string. To map back: a palindrome centered at i with radius p[i] in t corresponds to a substring of length p[i] in s starting at (i - p[i]) // 2.

Complexity summary

When to use which approach

If the problem involves palindromic substrings and you just need the longest one, expand-around-center is simplest. If you need to query whether arbitrary substrings are palindromes, typically as a subroutine for a partitioning or counting problem, build the boolean DP table. If the problem involves palindromic subsequences, you must use the interval DP with the match/no-match recurrence. And if constraints are very large and you only care about substrings, Manacher's gives you linear time.

The unifying theme across all these problems is that palindrome structure is inherently recursive: a palindrome is two matching characters wrapped around a smaller palindrome. That is why DP appears so naturally here: the subproblem structure is baked into the definition of what a palindrome is.

Recognizing this pattern

You're probably looking at palindrome DP when:

• The word palindrome appears in the problem along with longest/shortest/count/partition.
• The natural subproblem is "is s[i..j] a palindrome?", a 2D table indexed by interval endpoints.
• The recurrence relies on the fact that s[i..j] is a palindrome iff s[i] == s[j] and s[i+1..j-1] is.
• A brute-force "check every substring" would be $O(n^3)$, but constraints around $n \le 10^3$ allow $O(n^2)$ time and space.

Common templates:

• Boolean palindrome table: is_pal[i][j] = s[i]==s[j] and is_pal[i+1][j-1], used as a subroutine. Example: Palindromic Substrings.
• Longest palindromic subsequence: interval DP with dp[i][j] = dp[i+1][j-1] + 2 on match, else max(dp[i+1][j], dp[i][j-1]). Example: Longest Palindromic Subsequence.
• Expand around center: try each center and grow outward; $O(n^2)$ time, $O(1)$ space. Example: Longest Palindromic Substring.
• Partition with min cuts: combine the palindrome table with a 1D DP over prefixes. Example: Palindrome Partitioning II.
• Insertions/deletions to make palindrome: answer equals n - LPS(s), where LPS is longest palindromic subsequence. Example: Minimum Insertion Steps to Make a String Palindrome.