Problem

Given a string s, in one step you can delete any character from the string. Return the minimum number of deletions required to make s a palindrome.

A Palindrome String is one that reads the same backward as well as forward.

Examples

Example 1:

1
2
3
4
5

Input:
s = "zzazz"
Output:
0
Explanation: The string "zzazz" is already a palindrome, so no deletions are needed.

Example 2:

1
2
3
4
5

Input:
s = "mbadm"
Output:
2
Explanation: Deleting 'b' and 'm' makes "adm" or "bad" which can be rearranged to form a palindrome.

Example 3:

1
2
3
4
5

Input:
s = "leetcode"
Output:
5
Explanation: Deleting 5 characters can make the string a palindrome.

Similar Problems

Minimum Insertion Steps to Make a String Palindrome Minimum Insertion OR Deletion Steps to Make a String Palindrome

Solution

Method 1 – Recursion

To find the minimum number of deletions needed to make a substring a palindrome, we use a recursive approach:

  • If the characters at the current left and right positions are equal, move inward and solve for the substring.
  • If not, try deleting a character at either end and take the minimum steps required for the resulting substrings, plus one for the deletion.

Recurrence

Let D[i..j] be the minimum number of deletions needed to make the substring from index i to j a palindrome:

  • D[i..j] = D[i+1..j-1] if s[i] == s[j]
  • D[i..j] = min(D[i..j-1], D[i+1..j]) + 1 otherwise

Base Case:

  • D[i,i] = 0 (a single character is already a palindrome)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    int minDeletions(string s) {
        return helper(s, 0, s.size() - 1);
    }
    int helper(const string& s, int i, int j) {
        if (i >= j) return 0;
        if (s[i] == s[j]) return helper(s, i + 1, j - 1);
        return 1 + min(helper(s, i + 1, j), helper(s, i, j - 1));
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    public int minDeletions(String s) {
        return helper(s, 0, s.length() - 1);
    }
    private int helper(String s, int i, int j) {
        if (i >= j) return 0;
        if (s.charAt(i) == s.charAt(j)) return helper(s, i + 1, j - 1);
        return 1 + Math.min(helper(s, i + 1, j), helper(s, i, j - 1));
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def minDeletions(self, s: str) -> int:
        def helper(i: int, j: int) -> int:
            if i >= j:
                return 0
            if s[i] == s[j]:
                return helper(i + 1, j - 1)
            return 1 + min(helper(i + 1, j), helper(i, j - 1))
        return helper(0, len(s) - 1)

Complexity

  • ⏰ Time complexity: O(2^N), because each character can be either included or excluded, leading to exponential subproblems.
  • 🧺 Space complexity: O(N), for the recursion stack.

Method 2 – Top Down DP (Memoization)

Intuition

The top-down DP approach uses recursion with memoization to avoid recomputing results for the same substring. By storing results for each substring, we efficiently solve overlapping subproblems and reduce the exponential time complexity of the naive recursive solution.

Approach

  1. Use a helper function that takes two indices, i and j, representing the current substring.
  2. If i >= j, return 0 (base case: single character or empty substring is a palindrome).
  3. If the result for (i, j) is already computed, return it from the memo table.
  4. If s[i] == s[j], recursively solve for the inner substring (i+1, j-1).
  5. Otherwise, try deleting either end and take the minimum of both options plus one.
  6. Store the result in the memo table and return it.
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int minDeletions(string s) {
        int n = s.size();
        vector<vector<int>> memo(n, vector<int>(n, -1));
        return helper(s, 0, n - 1, memo);
    }
    int helper(const string& s, int i, int j, vector<vector<int>>& memo) {
        if (i >= j) return 0;
        if (memo[i][j] != -1) return memo[i][j];
        if (s[i] == s[j]) return memo[i][j] = helper(s, i + 1, j - 1, memo);
        return memo[i][j] = 1 + min(helper(s, i + 1, j, memo), helper(s, i, j - 1, memo));
    }
};
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public int minDeletions(String s) {
        int n = s.length();
        Integer[][] memo = new Integer[n][n];
        return helper(s, 0, n - 1, memo);
    }
    private int helper(String s, int i, int j, Integer[][] memo) {
        if (i >= j) return 0;
        if (memo[i][j] != null) return memo[i][j];
        if (s.charAt(i) == s.charAt(j)) return memo[i][j] = helper(s, i + 1, j - 1, memo);
        return memo[i][j] = 1 + Math.min(helper(s, i + 1, j, memo), helper(s, i, j - 1, memo));
    }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def minDeletions(self, s: str) -> int:
        memo: dict[tuple[int, int], int] = {}
        def helper(i: int, j: int) -> int:
            if i >= j:
                return 0
            if (i, j) in memo:
                return memo[(i, j)]
            if s[i] == s[j]:
                memo[(i, j)] = helper(i + 1, j - 1)
            else:
                memo[(i, j)] = 1 + min(helper(i + 1, j), helper(i, j - 1))
            return memo[(i, j)]
        return helper(0, len(s) - 1)

Complexity

  • ⏰ Time complexity: O(N^2), because there are O(N^2) unique substring pairs and each is computed once due to memoization.
  • 🧺 Space complexity: O(N^2), for the memoization table storing results for all substring pairs.

Method 3 – Dynamic Programming (Bottom-Up)

We can use a DP table to store the minimum deletions needed for every substring. For each substring, if the boundary characters match, we use the result for the inner substring. Otherwise, we take the minimum deletions from either side plus one.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int minDeletions(string s) {
        int n = s.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i + len - 1 < n; ++i) {
                int j = i + len - 1;
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    public int minDeletions(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];
        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] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n - 1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def minDeletions(self, s: str) -> int:
        n: int = len(s)
        dp: list[list[int]] = [[0] * n for _ in range(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]
                else:
                    dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1])
        return dp[0][n - 1] if n > 0 else 0

Complexity

  • ⏰ Time complexity: O(n^2) — We fill a DP table for all substrings.
  • 🧺 Space complexity: O(n^2) — The DP table stores results for all substring pairs.