Minimum Deletions in a String to make it a Palindrome

Mechanism

A string of length n can always be turned into a palindrome by deleting characters; the fewest deletions equal n minus the length of the longest palindromic subsequence (LPS) already hiding inside it. Keeping the LPS untouched and deleting every other character is both sufficient and optimal, because any palindrome formed by deletion is itself a palindromic subsequence of the original string — so the largest one you can preserve is the LPS, and everything else must go.

Recognize the pattern

• Phrasing is "minimum deletions/insertions to make a string a palindrome."
• Characters can be removed (or added) but never reordered.
• The answer requested is a count, not the resulting palindrome.
• n up to ~1000 signals an O(n²) interval DP is expected, not exponential enumeration.

Brute force → optimal

Brute force: enumerate every subsequence, check if it is a palindrome, keep the longest one, then answer = n minus that length. There are 2ⁿ subsequences, each checked in O(n), giving O(2ⁿ·n) time — usable only for tiny n.

Optimal: reduce to the Longest Palindromic Subsequence (LPS) of s, computed either directly with interval DP or as the Longest Common Subsequence (LCS) of s and reverse(s) — a palindromic subsequence read forwards equals itself read backwards, so it is also a common subsequence of s and its reverse. Both formulations run in O(n²) time and O(n²) space (reducible to O(n) space).

Complexity, derived from first principles

Let dp[i][j] = length of the LPS inside substring s[i..j]. There are O(n²) index pairs (i ≤ j), and each cell is filled in O(1) from smaller subproblems:

dp[i][i] = 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])

O(n²) cells × O(1) work = O(n²) time. The table itself needs O(n²) space; since row i only reads rows i and i+1, this can be compressed to O(n) with two rolling arrays. Final answer = n − dp[0][n-1].

Traced example: "cddpd" (n = 5)

Indices: c(0) d(1) d(2) p(3) d(4). Filling dp by increasing substring length:

LPS length = dp[0][4] = 3 (the subsequence "ddd" from positions 1,2,4). Minimum deletions = 5 − 3 = 2, matching the worked answer of deleting "c" and "p".

Java implementation

class Solution {
    public int minDeletions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) dp[i][i] = 1;
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = (len == 2 ? 0 : dp[i + 1][j - 1]) + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        int lps = n == 0 ? 0 : dp[0][n - 1];
        return n - lps;
    }
}

Pitfalls

• Forgetting the base case when len == 2: dp[i+1][j-1] would index an empty (invalid) interval; treat it as 0, not dp[i][i].
• Filling the table in the wrong order (by row instead of by increasing substring length) reads uncomputed cells.
• Confusing this with edit distance to a fixed target palindrome — here the target palindrome is unknown and must be discovered via LPS.
• Assuming greedy two-pointer deletion (mismatched ends → always delete one) is optimal without memoizing both branches; it degrades to exponential time without DP/memoization.

When to use / when not — trade-offs

Use interval DP on dp[i][j] (or LCS with the reverse) whenever the problem asks for a count of edits (insertions and/or deletions, which are symmetric here) to reach a palindrome, for n up to a few thousand. It is simple, correct, and O(n²) time/space.

vs. Manacher's algorithm: Manacher finds the longest palindromic substring (contiguous) in O(n), but that is a different quantity — it cannot answer this question, since the kept characters here need not be contiguous.

vs. plain LCS(s, reverse(s)): mathematically equivalent and often already implemented as a library routine, but costs an extra O(n) reversal and an extra mental mapping step; the direct LPS recurrence avoids that indirection and is easier to trace during an interview.

Takeaways

• Minimum deletions to palindrome = n − LPS(s); never solve it as an isolated problem, recognize it as LPS in disguise.
• LPS(s) = LCS(s, reverse(s)); both are O(n²) time/space, compressible to O(n) space.
• Fill interval DP tables by increasing substring length, not by row, so smaller intervals are ready when needed.

Recall: Why does keeping the longest palindromic subsequence and deleting the rest always give the minimum number of deletions?

Compiled from standard interview-prep DP treatments of Longest Palindromic Subsequence and its reduction to LCS(s, reverse(s)).