Minimum Insertion OR Deletion Steps to Make a String Palindrome

Problem

Given a string s, in one step you can either insert or delete any character at any index of the string. Return the minimum number of insertions or 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 operations are needed.

Example 2:

1
2
3
4
5


Input:
s = "mbadm"
Output:
2
Explanation: Two operations (insertions or deletions) can make the string a palindrome.

Example 3:

1
2
3
4
5


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

Solution

Method 1 – Recursion

To find the minimum number of insertions or 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 inserting or deleting a character at either end and take the minimum steps required for the resulting substrings, plus one for the operation.

Recurrence

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

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

Base Case:

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

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution {
public:
    int minOperations(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));
    }
};

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution {
    public int minOperations(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));
    }
}

Python

1
2
3
4
5
6
7
8
9


class Solution:
    def minOperations(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

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

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
    public int minInsertDeleteToPalindrome(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));
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution {
public:
    int minInsertDeleteToPalindrome(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));
    }
};

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def minInsertDeleteToPalindrome(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 (Edit Distance without Replace)

Intuition

To make a string palindrome using the minimum number of insertions or deletions, we can model the problem as transforming the string into its reverse using only insert and delete operations (no replacements). This is similar to the edit distance problem, but without the replace operation. The minimum number of operations required is the difference between the length of the string and the length of its Longest Common Subsequence (LCS) with its reverse. The LCS represents the largest part of the string that is already a palindrome, and the remaining characters must be inserted or deleted to achieve a palindrome.

For example, consider S = “ababcac” and its reverse S’ = “cacbaba”. We can transform S into S’ as follows:

1

"ababcac" > delete(4) => "ababac" > delete(5) => "ababa" > insert(0,c) => "cababa" > insert(2, c) => "cacbaba"

So we need 4 operations to transform S into S’ and hence into a palindrome.

Approach

To solve this problem, we use dynamic programming to find the length of the Longest Common Subsequence (LCS) between the string and its reverse. The LCS represents the largest palindromic part of the string. The minimum number of insertions or deletions required is the difference between the length of the string and the length of its LCS with its reverse.

Here are the steps:

Reverse the input string to get rev.
Initialize a DP table dp of size (n+1) x (n+1) where n is the length of the string.
For each character position i in the original string and j in the reversed string:
- If s[i-1] == rev[j-1], set dp[i][j] = dp[i-1][j-1] + 1.
- Otherwise, set dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
After filling the DP table, the value at dp[n][n] gives the length of the LCS.
The answer is n - dp[n][n], which is the minimum number of insertions or deletions needed to make the string a palindrome.

Code

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


class Solution {
public:
    int minInsertDeleteToPalindrome(string s) {
        string rev = s;
        reverse(rev.begin(), rev.end());
        int n = s.size();
        vector<vector<int>> dp(n+1, vector<int>(n+1, 0));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                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 n - dp[n][n];
    }
};

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


class Solution {
    public int minInsertDeleteToPalindrome(String s) {
        String rev = new StringBuilder(s).reverse().toString();
        int n = s.length();
        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] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return n - dp[n][n];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def minInsertDeleteToPalindrome(self, s: str) -> int:
        rev: str = s[::-1]
        n: int = len(s)
        dp: list[list[int]] = [[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 n - dp[n][n]

Complexity

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

Problem#

Examples#

Similar Problems#

Solution#

Method 1 – Recursion#

Recurrence#

C++#

Java#

Python#

Complexity#

Method 2 – Top Down DP (Memoization)#

Intuition#

Approach#

Java#

C++#

Python#

Complexity#

Method 3 – Dynamic Programming (Edit Distance without Replace)#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Similar Problems

Solution

Method 1 – Recursion

Recurrence

C++

Java

Python

Complexity

Method 2 – Top Down DP (Memoization)

Intuition

Approach

Java

C++

Python

Complexity

Method 3 – Dynamic Programming (Edit Distance without Replace)

Intuition

Approach

Code

Complexity