Minimum Insertion Steps to Make a String Palindrome
HardPrompt
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.
Example 1:
Input: s = "zzazz"
Output: 0
Explanation: The string "zzazz" is already palindrome we do not need any insertions.Example 2:
Input: s = "mbadm"
Output: 2
Explanation: String can be "mbdadbm" or "mdbabdm".Example 3:
Input: s = "leetcode"
Output: 5
Explanation: Inserting 5 characters the string becomes "leetcodocteel".
Constraints:
1 <= s.length <= 500sconsists of lowercase English letters.
Approaches
4 approaches with complexity analysis and trade-offs.
This approach uses an iterative, bottom-up method to solve the problem. It builds the solution from smaller subproblems to larger ones using a 2D DP table, avoiding recursion entirely. The recurrence relation is the same as in the previous approaches.
Algorithm
- Create a 2D DP table,
dp[n][n], wheredp[i][j]will store the minimum insertions fors[i...j]. - The base cases,
dp[i][i] = 0, are implicitly handled by initializing the array with zeros. - Iterate through substring lengths
lenfrom 2 ton. - For each
len, iterate through all possible start indicesifrom0ton-len. - Calculate the end index
j = i + len - 1. - Apply the transition formula:
- If
s[i] == s[j], thendp[i][j] = dp[i+1][j-1]. - If
s[i] != s[j], thendp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]).
- If
- The final answer is
dp[0][n-1].
Walkthrough
Instead of a top-down recursive approach, we can solve the problem iteratively in a bottom-up fashion. We use a 2D array dp[n][n], where dp[i][j] stores the minimum insertions to make s[i...j] a palindrome. We fill this table for substrings of increasing length. Substrings of length 1 are already palindromes, so dp[i][i] = 0. We then compute the values for substrings of length 2, then 3, and so on, up to n. When calculating dp[i][j], the values for the smaller subproblems it depends on (dp[i+1][j-1], dp[i+1][j], dp[i][j-1]) will have already been computed. The final result for the entire string s[0...n-1] is stored in dp[0][n-1].
class Solution { public int minInsertions(String s) { int n = s.length(); int[][] dp = new int[n][n]; for (int len = 2; len <= n; len++) { for (int i = 0; i <= n - len; 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]; }}Complexity
Time
O(n^2). The nested loops iterate through all `O(n^2)` subproblems, and each calculation is constant time.
Space
O(n^2) for the 2D DP table.
Trade-offs
Pros
Avoids recursion overhead, which can make it slightly faster in practice than memoization.
Can be more intuitive for those who prefer iterative solutions.
Cons
Requires O(n^2) space, same as the memoization approach.
Solutions
Solution
class Solution {private Integer[][] f;private String s;public int minInsertions(String s) { this.s = s; int n = s.length(); f = new Integer[n][n]; return dfs(0, n - 1); }private int dfs(int i, int j) { if (i >= j) { return 0; } if (f[i][j] != null) { return f[i][j]; } int ans = 1 << 30; if (s.charAt(i) == s.charAt(j)) { ans = dfs(i + 1, j - 1); } else { ans = Math.min(dfs(i + 1, j), dfs(i, j - 1)) + 1; } return f[i][j] = ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.