Problem

Given a string s. In one step you can insert any character at any index of the string.

Return the minimum number of steps to make s 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 palindrome we don't need any insertions.

Example 2:

1
2
3
4
5

Input:
s = "mbadm"
Output:
2
Explanation: String can be "mbdadbm" or "mdbabdm".

Example 3:

1
2
3
4
5

Input:
s = "leetcode"
Output:
5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".

Similar Problems

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

Solution

Method 1 – Recursion

The minimum number of insertions required to make a substring palindrome can be defined recursively:

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

Recurrence

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

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

Base Case:

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

Code

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

class Solution {

	public int minInsertions(String s) {
		return helper(s, 0, s.length() - 1, memo);
	}

	private int helper(String s, int i, int j) {
		if (i >= j) {
			return 0;
		}

		return s.charAt(i) == s.charAt(j) ? helper(s, i + 1, j - 1) : 1 + Math.min(helper(s, i + 1, j), helper(s, i, j - 1));
	}
}
1
2
3
4
5
6
7

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

Complexity

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

Method 2 - Top Down DP

If we observe the above approach carefully, we can find that it exhibits overlapping subproblems. Suppose we want to find the minimum number of insertions in string “abcde”:

graph TD;

T(fabcdef) --- A(abcde)
A --- B(bcde) & C(abcd)
B --- D(cde) & E(bcd)
C --- F(bcd) & G(abc)
D --- H(de) & I(cd)
E --- J(cd) & K(bc)
F --- L(...)
G --- M(...)
H --- N(...)
I --- O(...)
J --- P(...)
K --- Q(...)

style E fill:#00758f
style F fill:#00758f
style I fill:#010aaa
style J fill:#010aaa

Code

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

class Solution {
public:
    vector<vector<int>> memo;
    int dp(string &s,int i,int j)
    {
        if(i>=j)							//Base case.
            return 0;
        if(memo[i][j]!=-1)					//Check if we have already calculated the value for the pair `i` and `j`.
            return memo[i][j];
        return memo[i][j]=s[i]==s[j]?dp(s,i+1,j-1):1+min(dp(s,i+1,j),dp(s,i,j-1));		//Recursion as mentioned above.
    }
    int minInsertions(string s) 
    {
        memo.resize(s.length(),vector<int>(s.length(),-1));
        return dp(s,0,s.length()-1);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {

	public int minInsertions(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) { //Base case.
			return 0;
		}

		if (memo[i][j] != null) {
			return memo[i][j];
		}

		return memo[i][j] = s.charAt(i) == s.charAt(j) ? helper(s, i + 1, j - 1, memo) : 1 + Math.min(helper(s, i + 1, j, memo), helper(s, i, j - 1, memo));
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def minInsertions(self, s: str) -> int:
        memo: dict[tuple[int, int], int] = {}

        def dp(left: int, right: int) -> int:
            if left >= right:
                return 0
            if (left, right) in memo:
                return memo[(left, right)]
            if s[left] == s[right]:
                memo[(left, right)] = dp(left + 1, right - 1)
            else:
                insert_left: int = dp(left + 1, right)
                insert_right: int = dp(left, right - 1)
                memo[(left, right)] = 1 + min(insert_left, insert_right)
            return memo[(left, right)]

        return dp(0, len(s) - 1)

Complexity

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

Method 3 - Bottom-up DP

Intuition

The bottom-up DP approach works by solving smaller subproblems first and building up to the solution for the entire string. We use a table to store the minimum insertions needed for every substring, starting from length 2 up to the full string. By filling the table in increasing order of substring length, we ensure that all required subproblems are already solved when needed.

Approach

  1. Create a 2D DP table dp[i][j] where each entry represents the minimum insertions needed to make the substring s[i..j] a palindrome.
  2. Initialize all dp[i][i] = 0 since a single character is already a palindrome.
  3. Iterate over all possible substring lengths from 2 to N.
  4. For each substring, check:
    • If s[i] == s[j], then dp[i][j] = dp[i+1][j-1] (no insertion needed).
    • Else, dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]) (insert at either end).
  5. The answer is dp[0][N-1] for the whole string.
  6. Edge cases: Empty string or single character string returns 0.
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int minInsertions(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];
    }
};
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {

	public int minInsertions(String s) {
		int n = s.length();
		int[][] dp = new int[n][n];
		// Length of substring (2 to n)
		for (int len = 2; len <= n; len++) {
			// i = Starting index of substring
			for (int i = 0; i + len - 1 < n; i++) {
			    // j - Ending index of substring
				int j = i + len - 1;
				// If characters match, use previous result
				if (s.charAt(i) == s.charAt(j)) {
					dp[i][j] = dp[i + 1][j - 1];
				} else {
					// Minimum insertions from either side
					dp[i][j] = 1 + Math.min(dp[i + 1][j], dp[i][j - 1]);
				}
			}
		}

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

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

class Solution:
    def minInsertions(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), because we fill a DP table of size N x N and each entry is computed in constant time.
  • 🧺 Space complexity: O(N^2), for the DP table storing results for all substring pairs.