Minimum number of deletions in a string to make it palindrome

Link: Minimum Deletions to Make a String Palindrome

Statement

Given a string s, find the minimum number of characters that need to be deleted to make it a palindrome.

Intuition

To make a string a palindrome with minimum deletions, we should keep the Longest Palindromic Subsequence (LPS) and delete the remaining characters.

Formula:

Minimum Deletions = Length of string - Length of Longest Palindromic Subsequence (LPS)

To find the LPS, compute the Longest Common Subsequence (LCS) between the string and its reverse.

Recursive Approach

Logic:

• Compute LCS between s and reverse(s) recursively.

• Subtract the LCS length from the total string length to get minimum deletions.

class Solution {
    int lcs(String s1, String s2, int i, int j) {
        if (i == 0 || j == 0) return 0;

        if (s1.charAt(i - 1) == s2.charAt(j - 1))
            return 1 + lcs(s1, s2, i - 1, j - 1);
        else
            return Math.max(lcs(s1, s2, i - 1, j), lcs(s1, s2, i, j - 1));
    }

    int minimumNumberOfDeletions(String s) {
        String rev = new StringBuilder(s).reverse().toString();
        int n = s.length();
        int lps = lcs(s, rev, n, n);
        return n - lps;
    }
}

Time Complexity: Exponential O(2^n)
Space Complexity: O(n) (call stack)

Memoization (Top-down DP)

Logic:

• Use a 2D DP array dp[i][j] to store LCS values.

• Avoid recomputation by memoizing results.

class Solution {
    int[][] dp;

    int lcs(String s1, String s2, int i, int j) {
        if (i == 0 || j == 0) return 0;
        if (dp[i][j] != -1) return dp[i][j];

        if (s1.charAt(i - 1) == s2.charAt(j - 1))
            return dp[i][j] = 1 + lcs(s1, s2, i - 1, j - 1);
        else
            return dp[i][j] = Math.max(lcs(s1, s2, i - 1, j), lcs(s1, s2, i, j - 1));
    }

    int minimumNumberOfDeletions(String s) {
        int n = s.length();
        String rev = new StringBuilder(s).reverse().toString();
        dp = new int[n + 1][n + 1];

        for (int[] row : dp)
            Arrays.fill(row, -1);

        int lps = lcs(s, rev, n, n);
        return n - lps;
    }
}

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

Tabulation (Bottom-up DP)

Logic:

• Build the LCS table iteratively.

• dp[i][j] stores LCS of the first i characters of s and j characters of rev(s).

class Solution {
    int minimumNumberOfDeletions(String s) {
        int n = s.length();
        String rev = new StringBuilder(s).reverse().toString();

        int[][] dp = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == rev.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return n - dp[n][n];
    }
}

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

Time and Space Complexity Summary

Dry Run Example

Input: s = "aebcbda"
Reversed: rev = "adbcbea"
LCS = "abcba" → Length = 5
Minimum deletions = 7 - 5 = 2

Summary

• Find the Longest Palindromic Subsequence by computing LCS of s and reverse(s).

• Subtract LCS length from total string length to get minimum deletions.

• Use Tabulation in interviews or contests for optimal results.