DP Palindrome Problems: LPS, Partition, Count Substrings & Shortest Palindrome

Palindrome problems sit at the intersection of string manipulation and dynamic programming. They appear frequently in interviews because they test both DP thinking and string insight. This post covers the four most important palindrome DP patterns.

1. Longest Palindromic Subsequence (LPS)

Problem: Given a string s, find the length of the longest palindromic subsequence. (LeetCode 516)

A subsequence is not contiguous. For example, in "bbbab", the LPS is "bbbb" with length 4.

Approach 1: Reverse + LCS

The LPS of s equals the LCS (longest common subsequence) of s and reverse(s).

def longest_palindrome_subseq(s):
    n = len(s)
    rev = s[::-1]

    # LCS of s and reverse(s)
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if s[i - 1] == rev[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[n][n]

Time: O(n^2) | Space: O(n^2), reducible to O(n)

Approach 2: Direct Interval DP

dp[i][j] = LPS length of s[i..j].

def longest_palindrome_subseq_interval(s):
    n = len(s)
    dp = [[0] * n for _ in range(n)]

    # Every single character is a palindrome of length 1
    for i in range(n):
        dp[i][i] = 1

    # Fill diagonals from bottom-left to top-right
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            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]

Space-Optimised to O(n)

def longest_palindrome_subseq_opt(s):
    n = len(s)
    dp = [0] * n
    dp_prev = [0] * n

    for i in range(n - 1, -1, -1):
        new_dp = [0] * n
        new_dp[i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                new_dp[j] = dp[j - 1] + 2  # dp is the row i+1
            else:
                new_dp[j] = max(dp[j], new_dp[j - 1])
        dp = new_dp

    return dp[n - 1] if n > 0 else 0

---

2. Longest Palindromic Substring

Problem: Find the longest palindromic substring (contiguous). (LeetCode 5)

Expand Around Center

Every palindrome has a center. There are 2n - 1 possible centers (n for odd-length, n-1 for even-length). Expand outward from each center.

def longest_palindrome(s):
    n = len(s)
    if n == 0:
        return ""

    start, max_len = 0, 1

    def expand(left, right):
        nonlocal start, max_len
        while left >= 0 and right < n 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(n):
        expand(i, i)      # odd-length palindromes
        expand(i, i + 1)  # even-length palindromes

    return s[start:start + max_len]

Time: O(n^2) | Space: O(1)

DP Table Approach

def longest_palindrome_dp(s):
    n = len(s)
    if n <= 1:
        return s

    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1

    # All single characters
    for i in range(n):
        dp[i][i] = True

    # Check length 2
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start, max_len = i, 2

    # Check lengths 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
                start, max_len = i, length

    return s[start:start + max_len]

---

3. Palindrome Partitioning II (Minimum Cuts)

Problem: Given a string s, return the minimum number of cuts needed so every substring is a palindrome. (LeetCode 132)

Approach: Two Arrays

First, precompute whether s[i..j] is a palindrome. Then, find minimum cuts.

def min_cut(s):
    n = len(s)
    if n <= 1:
        return 0

    # is_pal[i][j] = True if s[i..j] is a palindrome
    is_pal = [[False] * n for _ in range(n)]
    for i in range(n):
        is_pal[i][i] = True
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                is_pal[i][j] = (length == 2) or is_pal[i + 1][j - 1]

    # cuts[i] = min cuts for s[0..i]
    cuts = list(range(n))  # worst case: cut every character

    for i in range(1, 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]

Time: O(n^2) | Space: O(n^2)

Optimised: Build Palindromes On-the-Fly

We can expand around centers while updating cuts, avoiding the separate is_pal table:

def min_cut_optimised(s):
    n = len(s)
    cuts = list(range(-1, n))  # cuts[i+1] = min cuts for s[0..i], cuts[0] = -1

    for center in range(n):
        # Odd-length palindromes
        left, right = center, center
        while left >= 0 and right < n and s[left] == s[right]:
            cuts[right + 1] = min(cuts[right + 1], cuts[left] + 1)
            left -= 1
            right += 1

        # Even-length palindromes
        left, right = center, center + 1
        while left >= 0 and right < n and s[left] == s[right]:
            cuts[right + 1] = min(cuts[right + 1], cuts[left] + 1)
            left -= 1
            right += 1

    return cuts[n]

Time: O(n^2) | Space: O(n)

---

4. Count Palindromic Substrings

Problem: Count the number of palindromic substrings in s. (LeetCode 647)

Expand Around Center

def count_substrings(s):
    n = len(s)
    count = 0

    for center in range(n):
        # Odd-length
        left, right = center, center
        while left >= 0 and right < n and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1

        # Even-length
        left, right = center, center + 1
        while left >= 0 and right < n and s[left] == s[right]:
            count += 1
            left -= 1
            right += 1

    return count

Time: O(n^2) | Space: O(1)

Manacher’s Algorithm: O(n)

Manacher’s finds the longest palindrome centered at each position in linear time. It exploits symmetry: if you are inside a known palindrome, the radius at your position mirrors the radius at your “mirror” position.

def count_substrings_manacher(s):
    # Transform: "abc" -> "^#a#b#c#$"
    t = '^#' + '#'.join(s) + '#$'
    n = len(t)
    p = [0] * n  # p[i] = radius of palindrome centered at t[i]
    center = right = 0

    for i in range(1, n - 1):
        mirror = 2 * center - i
        if i < right:
            p[i] = min(right - i, p[mirror])

        # Expand
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1

        # Update center
        if i + p[i] > right:
            center, right = i, i + p[i]

    # Count: each palindrome centered at '#' positions has even length,
    # each at character positions has odd length
    count = 0
    for i in range(1, n - 1):
        # p[i] at a '#' position: p[i]//2 even-length palindromes
        # p[i] at a char position: (p[i]+1)//2 odd-length palindromes
        count += (p[i] + 1) // 2 if t[i] != '#' else p[i] // 2

    return count

Time: O(n) | Space: O(n)

---

5. Shortest Palindrome

Problem: Given a string s, find the shortest palindrome you can form by adding characters only to the front. (LeetCode 214)

Key Insight

Find the longest palindrome prefix of s. Everything after that prefix needs to be reversed and prepended.

KMP Approach

Build the string s + "#" + reverse(s) and compute the KMP failure function. The last value of the failure array gives the length of the longest palindrome prefix.

def shortest_palindrome(s):
    if not s:
        return s

    rev = s[::-1]
    combined = s + '#' + rev

    # KMP failure function
    n = len(combined)
    fail = [0] * n

    for i in range(1, n):
        j = fail[i - 1]
        while j > 0 and combined[i] != combined[j]:
            j = fail[j - 1]
        if combined[i] == combined[j]:
            j += 1
        fail[i] = j

    # Length of longest palindrome prefix
    pal_len = fail[-1]

    # Add the remaining suffix (reversed) to the front
    suffix = s[pal_len:]
    return suffix[::-1] + s

Time: O(n) | Space: O(n)

Example Walkthrough

For s = "aacecaaa":

1. rev = "aaacecaa"
2. combined = "aacecaaa#aaacecaa"
3. KMP failure function: [0,1,0,0,0,1,2,2,0,1,2,2,3,4,5,6,7]
4. fail[-1] = 7, so the palindrome prefix is s[0:7] = "aacecaa"
5. Remaining: s[7:] = "a", reversed: "a"
6. Result: "a" + "aacecaaa" = "aaacecaaa"

Rolling Hash Alternative

def shortest_palindrome_hash(s):
    if not s:
        return s

    n = len(s)
    MOD = (1 << 61) - 1
    BASE = 131
    prefix_hash = 0
    suffix_hash = 0
    power = 1
    best = 0

    for i in range(n):
        prefix_hash = (prefix_hash * BASE + ord(s[i])) % MOD
        suffix_hash = (suffix_hash + ord(s[i]) * power) % MOD
        power = (power * BASE) % MOD

        if prefix_hash == suffix_hash:
            best = i + 1

    suffix = s[best:]
    return suffix[::-1] + s

Time: O(n) | Space: O(1) (ignoring output string)

---

Palindrome DP Comparison

Problem	State	Time	Space	Key Technique
Longest Palindromic Subseq	dp[i][j] interval	O(n^2)	O(n)	LCS with reverse
Longest Palindromic Substr	center expansion	O(n^2)	O(1)	Expand around center
Min Palindrome Cuts	cuts[i]	O(n^2)	O(n)	Expand + update cuts
Count Palindromic Substr	center expansion	O(n^2)	O(1)	Count during expansion
Shortest Palindrome	KMP failure	O(n)	O(n)	s + # + rev(s)

---

Common Mistakes

1. Confusing subsequence and substring: Subsequences are not contiguous, substrings are.
2. Manacher off-by-one: The sentinel characters ^ and $ must be different from # and from all characters in s.
3. Palindrome partitioning: cuts[i] starts at i (worst case), not at n.
4. KMP separator: The # in s + "#" + rev(s) must not appear in s to prevent false matches.
5. Even vs. odd palindromes: Always check both center types.

---

Practice Problems

Problem	Platform	Difficulty
Longest Palindromic Subsequence	LeetCode 516	Medium
Longest Palindromic Substring	LeetCode 5	Medium
Palindrome Partitioning II	LeetCode 132	Hard
Palindromic Substrings	LeetCode 647	Medium
Shortest Palindrome	LeetCode 214	Hard
Palindrome Partitioning	LeetCode 131	Medium
Palindrome Partitioning IV	LeetCode 1745	Hard
Longest Palindrome by Concatenating Two Letter Words	LeetCode 2131	Medium