Palindrome Removal: Minimum Deletions DP

Key Insights

The minimum deletions to make a palindrome equals the string length minus the Longest Palindromic Subsequence (LPS), which cleverly reduces to finding the LCS of a string with its reverse.
The 2D DP approach builds solutions for progressively longer substrings, with the recurrence hinging on whether endpoint characters match.
Space optimization from O(n²) to O(n) is achievable using a rolling array technique, though the readability trade-off often isn’t worth it in production code.

Problem Introduction

Given a string, find the minimum number of characters you need to delete so that the remaining characters form a palindrome. This problem appears frequently in technical interviews and has practical applications beyond algorithmic puzzles.

In bioinformatics, comparing DNA sequences often involves finding the longest common structure between a sequence and its complement. Text editors use similar algorithms for diff operations and suggesting corrections. Data compression algorithms leverage palindromic structures for efficient encoding.

The goal is straightforward: given string s of length n, compute the minimum deletions required to transform s into a palindrome. For example, given “aebcbda”, we can delete ’e’ and ’d’ to get “abcba”, so the answer is 2.

Key Insight: LCS Connection

Here’s the elegant mathematical insight that makes this problem tractable. Instead of thinking about what to delete, think about what to keep. We want to keep the longest possible subsequence that’s already a palindrome.

If the Longest Palindromic Subsequence (LPS) has length k, then we must delete exactly n - k characters. The problem transforms from “minimize deletions” to “maximize the palindromic subsequence.”

Now comes the clever reduction: finding the LPS of a string s is equivalent to finding the Longest Common Subsequence (LCS) between s and its reverse s'. Why does this work?

A palindrome reads the same forwards and backwards. Any common subsequence between a string and its reverse must, by definition, read the same in both directions. The longest such subsequence is our LPS.

def lcs(s1: str, s2: str) -> int:
    """Find length of Longest Common Subsequence between two strings."""
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[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[m][n]

def min_deletions_via_lcs(s: str) -> int:
    """Minimum deletions = length - LPS = length - LCS(s, reverse(s))."""
    lps_length = lcs(s, s[::-1])
    return len(s) - lps_length

This approach works, but we’re computing LCS on two strings of length n, which feels slightly indirect. Let’s formulate the LPS directly.

Dynamic Programming Formulation

We define our state as dp[i][j] representing the length of the longest palindromic subsequence in the substring s[i...j] (inclusive).

Base cases:

Single characters are palindromes of length 1: dp[i][i] = 1
Empty substrings (where i > j) have length 0: dp[i][j] = 0 when i > j

Recurrence relation: For a substring from index i to j:

If s[i] == s[j]: The endpoints match, so we can include both in our palindrome. dp[i][j] = dp[i+1][j-1] + 2
If s[i] != s[j]: The endpoints don’t match, so at least one must be excluded. dp[i][j] = max(dp[i+1][j], dp[i][j-1])

The key insight in the transition logic: when characters match, we’re essentially “wrapping” a smaller palindrome with matching bookends. When they don’t match, we try excluding each endpoint and take the better result.

def build_lps_table(s: str) -> list[list[int]]:
    """Build the complete DP table for Longest Palindromic Subsequence."""
    n = len(s)
    if n == 0:
        return [[]]
    
    # Initialize table with zeros
    dp = [[0] * n for _ in range(n)]
    
    # Base case: single characters
    for i in range(n):
        dp[i][i] = 1
    
    # Fill table for increasing substring lengths
    # length = 2, 3, ..., n
    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

Notice we iterate by substring length, not by index. This ensures that when we compute dp[i][j], all smaller subproblems (dp[i+1][j-1], dp[i+1][j], dp[i][j-1]) are already solved.

Implementation Walkthrough

Here’s the complete solution with detailed comments and the helper function to compute the final answer:

def min_deletions_for_palindrome(s: str) -> int:
    """
    Calculate minimum deletions to make string a palindrome.
    
    Time Complexity: O(n²) - we fill an n×n table
    Space Complexity: O(n²) - for the DP table
    
    Args:
        s: Input string
        
    Returns:
        Minimum number of characters to delete
    """
    n = len(s)
    
    # Edge cases
    if n <= 1:
        return 0
    
    # dp[i][j] = length of LPS in s[i:j+1]
    dp = [[0] * n for _ in range(n)]
    
    # Base case: every single character is a palindrome
    for i in range(n):
        dp[i][i] = 1
    
    # Process substrings of increasing length
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            
            if s[i] == s[j]:
                # Characters match: extend the inner palindrome
                # Special case for length 2: dp[i+1][j-1] would be dp[i+1][i]
                # which is 0 (invalid range), but 0 + 2 = 2 is correct
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                # Characters don't match: take best of excluding either end
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    
    # LPS length is dp[0][n-1]
    # Minimum deletions = total length - LPS length
    lps_length = dp[0][n - 1]
    return n - lps_length


def get_palindrome_after_deletion(s: str) -> str:
    """Reconstruct one possible palindrome after minimum deletions."""
    n = len(s)
    if n <= 1:
        return s
    
    # Build the DP table first
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    
    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])
    
    # Backtrack to find the actual palindrome
    result = []
    i, j = 0, n - 1
    
    while i <= j:
        if i == j:
            result.append(s[i])
            break
        elif s[i] == s[j]:
            result.append(s[i])
            i += 1
            j -= 1
        elif dp[i + 1][j] > dp[i][j - 1]:
            i += 1
        else:
            j -= 1
    
    # Build palindrome: result + reverse of result (minus middle if odd length)
    left_half = ''.join(result)
    if len(left_half) > 0 and dp[0][n-1] % 2 == 1:
        return left_half + left_half[-2::-1]
    return left_half + left_half[::-1]

Space Optimization

The standard approach uses O(n²) space, but we can reduce this to O(n) using a rolling array. The key observation: when computing row i, we only need values from row i+1.

def min_deletions_space_optimized(s: str) -> int:
    """
    Space-optimized version using O(n) space.
    
    Trade-off: Harder to read, can't reconstruct the actual palindrome.
    """
    n = len(s)
    if n <= 1:
        return 0
    
    # prev represents dp[i+1][*], curr represents dp[i][*]
    prev = [0] * n
    curr = [0] * n
    
    # Base case: single characters
    for i in range(n):
        prev[i] = 1  # This will be shifted as we iterate
    
    # We iterate i from n-1 down to 0
    for i in range(n - 2, -1, -1):
        curr[i] = 1  # dp[i][i] = 1
        
        for j in range(i + 1, n):
            if s[i] == s[j]:
                # dp[i][j] = dp[i+1][j-1] + 2
                # prev[j-1] is dp[i+1][j-1]
                curr[j] = prev[j - 1] + 2 if j > 0 else 2
            else:
                # dp[i][j] = max(dp[i+1][j], dp[i][j-1])
                # prev[j] is dp[i+1][j], curr[j-1] is dp[i][j-1]
                curr[j] = max(prev[j], curr[j - 1])
        
        prev, curr = curr, prev
    
    # After the loop, prev contains dp[0][*]
    return n - prev[n - 1]

Honestly, I rarely use this optimization in production. The O(n²) space is acceptable for most string lengths you’ll encounter, and the clarity of the 2D version makes debugging and maintenance far easier. Reserve this for competitive programming or memory-constrained environments.

Worked Example

Let’s trace through s = "aebcbda" step by step.

Index:  0   1   2   3   4   5   6
Char:   a   e   b   c   b   d   a

Initial DP table (diagonal = 1):
      0   1   2   3   4   5   6
    +---+---+---+---+---+---+---+
  0 | 1 |   |   |   |   |   |   |
  1 |   | 1 |   |   |   |   |   |
  2 |   |   | 1 |   |   |   |   |
  3 |   |   |   | 1 |   |   |   |
  4 |   |   |   |   | 1 |   |   |
  5 |   |   |   |   |   | 1 |   |
  6 |   |   |   |   |   |   | 1 |

Length 2: Check pairs (0,1), (1,2), ..., (5,6)
- s[0]='a' != s[1]='e': dp[0][1] = max(dp[1][1], dp[0][0]) = 1
- s[2]='b' != s[3]='c': dp[2][3] = 1
- s[3]='c' != s[4]='b': dp[3][4] = 1
...

Length 3: 
- s[2]='b', s[4]='b' match! dp[2][4] = dp[3][3] + 2 = 1 + 2 = 3

Length 7: Full string
- s[0]='a' == s[6]='a': dp[0][6] = dp[1][5] + 2 = 3 + 2 = 5

Final: LPS = 5, deletions = 7 - 5 = 2
Palindrome: "abcba" (delete 'e' and 'd')

This problem is a gateway to several related challenges:

Minimum Insertions: Instead of deleting characters, insert characters to make a palindrome. The answer is identical—n - LPS(s)—because each deletion can be viewed as an insertion in the reverse direction.

Palindrome Partitioning II: Find the minimum cuts to partition a string into palindromic substrings. This requires a different DP formulation but builds on similar palindrome-checking intuition.

Longest Palindromic Substring (not subsequence): Uses a different approach—expand around centers or Manacher’s algorithm.

For interview preparation, master the LPS/LCS connection first. It demonstrates you can recognize problem transformations, a skill interviewers value highly. Practice reconstructing the actual palindrome, not just computing its length—this tests your understanding of DP backtracking.