Minimum Insertion Steps to Make a String Palindrome

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".

Follow up

Lexicographically Smallest Palindrome by Minimum Insertions

Solution

Method 1 – Recursion

Intuition

If the first and last characters of the substring match, the problem reduces to the substring in between. If not, we must insert a character at either end and solve for the smaller substring, taking the minimum. This is a classic divide-and-conquer approach, but it recalculates many subproblems.

Approach

If the substring is empty or a single character, no insertions are needed.
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

Intuition

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

The recursive approach recalculates the same subproblems many times, leading to exponential time. By storing results for each substring in a memoization table, we avoid redundant work and reduce the time complexity to quadratic.

Approach

Use a 2D memoization table memo[i][j] to store the minimum insertions for substring s[i..j].
For each substring, if the characters at the ends match, inherit the result from the inner substring.
Otherwise, take the minimum of inserting at either end, plus one.
The answer is memo[0][n-1].

The recursion tree for a string like “abcde” shows many overlapping subproblems. For example, the substring “bcd” appears in multiple branches. Memoization ensures each is solved only once.

DP Table Example:

For string “abcde”, the DP table (showing minimum insertions for each substring) is filled diagonally:

	a	b	c	d	e
a	0	1	2	3	4
b		0	1	2	3
c			0	1	2
d				0	1
e					0

The value at (0,4) gives the answer for the whole string.

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 (Tabulation)

Intuition

The bottom-up DP approach builds the solution for all substrings of increasing length, filling a table diagonally. This ensures that when solving for a substring, all smaller substrings are already solved. The diagonal filling order is crucial for correctness.

Approach

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.
Initialize all dp[i][i] = 0 since a single character is already a palindrome.
Fill the table diagonally: for each gap from 1 to n-1, fill all substrings of that length.
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).
The answer is dp[0][n-1] for the whole string.
Edge cases: Empty string or single character string returns 0.

Table Filling Order Example:

For string “abcde”, the table is filled in this order:

Gap = 1: (0,1) (1,2) (2,3) (3,4) Gap = 2: (0,2) (1,3) (2,4) Gap = 3: (0,3) (1,4) Gap = 4: (0,4)

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.

Method 4 – Dynamic Programming via Longest Common Subsequence

We can also use Longest Common Subsequence Problem to solve this problem.

Intuition

The minimum number of insertions needed to make a string palindrome is equal to the number of characters not already part of a longest palindromic subsequence. The longest palindromic subsequence (LPS) of a string is the longest sequence that reads the same forward and backward and can be found by computing the LCS of the string and its reverse.

Approach

Let t be the reverse of the input string s.
Compute the length of the longest common subsequence (LCS) between s and t.
The answer is len(s) - LCS(s, t).

Code

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


class Solution {
public:
    int minInsertions(string s) {
        string t = s;
        reverse(t.begin(), t.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] == t[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


class Solution {
    public int minInsertions(String s) {
        String t = 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) == t.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 minInsertions(self, s: str) -> int:
        t = s[::-1]
        n = len(s)
        dp = [[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] == t[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), for filling the LCS DP table.
🧺 Space complexity: O(N^2), for the DP table.

Problem#

Examples#

Follow up#

Solution#

Method 1 – Recursion#

Intuition#

Approach#

Recurrence#

Code#

Complexity#

Method 2 - Top Down DP#

Intuition#

Approach#

Code#

Complexity#

Method 3 – Bottom-up DP (Tabulation)#

Intuition#

Approach#

C++#

Java#

Python#

Complexity#

Method 4 – Dynamic Programming via Longest Common Subsequence#

Intuition#

Approach#

Code#

Complexity#

Problem

Examples

Follow up

Solution

Method 1 – Recursion

Intuition

Approach

Recurrence

Code

Complexity

Method 2 - Top Down DP

Intuition

Approach

Code

Complexity

Method 3 – Bottom-up DP (Tabulation)

Intuition

Approach

C++

Java

Python

Complexity

Method 4 – Dynamic Programming via Longest Common Subsequence

Intuition

Approach

Code

Complexity