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.
This is the most efficient approach in terms of space. It's based on the key insight that the minimum number of insertions is equal to the length of the string minus the length of its Longest Palindromic Subsequence (LPS). We can then compute the LPS length using a space-optimized bottom-up DP, reducing space from O(n^2) to O(n).
Algorithm
- Realize that
min_insertions = n - length(LPS), where LPS is the Longest Palindromic Subsequence. - The problem is now to find the length of the LPS of
s. - Use a 1D array
dp[n]to store the LPS lengths. - Iterate
ifromn-1down to0. This corresponds to the row in a conceptual 2D DP table. - For each
i, iteratejfromi+1ton-1. - Use a
prevvariable to hold the value from the top-left diagonal cell (lps(i+1, j-1)). - The recurrence for LPS length is:
- If
s[i] == s[j],lps(i, j) = 2 + lps(i+1, j-1). - If
s[i] != s[j],lps(i, j) = max(lps(i+1, j), lps(i, j-1)).
- If
- After the loops,
dp[n-1]will contain the LPS length of the whole string. - Return
n - dp[n-1].
Walkthrough
A crucial observation transforms the problem: the characters that are part of the longest palindromic subsequence (LPS) of s already form a palindrome. We only need to add characters to mirror the ones not in the LPS. Thus, the number of insertions needed is n - length(LPS).
We can find the length of the LPS using dynamic programming. A standard 2D DP approach would take O(n^2) space. However, we can optimize this. When computing the LPS for a row i, we only need information from the previous row i+1 and the current row i. This dependency allows us to use only a 1D array, dp, to store the values for the current row being computed, effectively reducing space complexity to O(n).
class Solution { public int minInsertions(String s) { int n = s.length(); // The problem is equivalent to finding the length of the Longest Palindromic Subsequence (LPS). // minInsertions = n - length(LPS). // We find length of LPS using space-optimized DP. int[] dp = new int[n]; for (int i = n - 1; i >= 0; i--) { // Base case: LPS of a single character string is 1. dp[i] = 1; int prev = 0; // Stores dp[i+1][j-1] for (int j = i + 1; j < n; j++) { int temp = dp[j]; // Stores dp[i+1][j] if (s.charAt(i) == s.charAt(j)) { dp[j] = 2 + prev; } else { dp[j] = Math.max(dp[j], dp[j - 1]); } prev = temp; } } int lpsLength = dp[n - 1]; return n - lpsLength; }}Complexity
Time
O(n^2). The time complexity is dominated by the nested loops.
Space
O(n) for the 1D DP array.
Trade-offs
Pros
Most space-efficient solution.
Maintains the optimal O(n^2) time complexity.
Cons
The logic for space optimization can be less intuitive than the standard 2D DP approach.
A straightforward recursive approach that directly models the problem. For any substring, if the ends match, we solve for the inner substring. If they don't, we try inserting a character at either end and take the minimum of the two resulting subproblems.
Algorithm
- Define a recursive function
solve(s, i, j)which returns the minimum insertions for the substrings[i...j]. - Base Case: If
i >= j, the substring is empty or has one character. It's already a palindrome, so return 0. - Recursive Step:
- If
s.charAt(i) == s.charAt(j), the ends match. The problem reduces to the inner substring. Returnsolve(s, i + 1, j - 1). - If
s.charAt(i) != s.charAt(j), the ends don't match. We must insert a character. We take the minimum of two choices:- Make
s[i...j-1]a palindrome and add a matching character fors[j]. Cost:1 + solve(s, i, j - 1). - Make
s[i+1...j]a palindrome and add a matching character fors[i]. Cost:1 + solve(s, i + 1, j).
- Return
1 + min(solve(s, i + 1, j), solve(s, i, j - 1)).
- Make
- If
Walkthrough
This approach solves the problem by breaking it down into smaller, overlapping subproblems. We define a function solve(s, i, j) that computes the minimum insertions for the substring s[i...j]. The logic follows a simple decision process at each step. If the characters at the current endpoints i and j are the same, they form a palindromic pair, and we only need to solve the problem for the substring between them, s[i+1...j-1]. If they are different, we must perform an insertion. We can either insert a character to match s[i] or a character to match s[j]. This means we either solve for s[i+1...j] or s[i...j-1] and add one to the result for the insertion. We choose the option that yields the minimum number of insertions. The base case for the recursion is an empty or single-character string, which is already a palindrome and requires zero insertions.
class Solution { public int minInsertions(String s) { return solve(s, 0, s.length() - 1); } private int solve(String s, int i, int j) { if (i >= j) { return 0; } if (s.charAt(i) == s.charAt(j)) { return solve(s, i + 1, j - 1); } else { return 1 + Math.min(solve(s, i + 1, j), solve(s, i, j - 1)); } }}Complexity
Time
O(2^n), where n is the length of the string. In the worst-case scenario (a string with no matching characters), each call to `solve` for a substring of length `k` generates two calls for substrings of length `k-1`, leading to an exponential number of function calls.
Space
O(n), where n is the length of the string. This is due to the maximum depth of the recursion stack.
Trade-offs
Pros
Simple to understand and implement.
Directly translates the problem's definition into code.
Cons
Extremely inefficient due to a large number of redundant computations for the same subproblems.
Will result in a 'Time Limit Exceeded' error for all but the smallest input sizes.
This approach improves upon the brute-force recursion by using a memoization table (a 2D array) to store the results of subproblems. This avoids re-computation of the same subproblem, drastically reducing the time complexity.
Algorithm
- Create a 2D array
memo[n][n]to store the results of subproblems, initialized to a value likenullor-1. - Use the same recursive function
solve(s, i, j)as the brute-force approach. - Before computing the result for
(i, j), check ifmemo[i][j]already contains a valid result. If so, return it immediately. - If not, compute the result using the same recursive logic.
- Store the computed result in
memo[i][j]before returning it.
Walkthrough
The brute-force recursive solution suffers from solving the same subproblems multiple times. We can optimize this by using dynamic programming with memoization. We'll use a 2D array, memo, where memo[i][j] will store the minimum insertions needed for the substring s[i...j]. The recursive function's logic remains the same, but with one key difference: at the beginning of the function, we check if the result for the current state (i, j) has already been computed. If memo[i][j] is not null, we return the stored value. Otherwise, we compute the result, store it in memo[i][j], and then return it. This ensures that each of the O(n^2) possible subproblems is solved only once.
class Solution { private Integer[][] memo; public int minInsertions(String s) { int n = s.length(); memo = new Integer[n][n]; return solve(s, 0, n - 1); } private int solve(String s, int i, int j) { if (i >= j) { return 0; } if (memo[i][j] != null) { return memo[i][j]; } if (s.charAt(i) == s.charAt(j)) { memo[i][j] = solve(s, i + 1, j - 1); } else { memo[i][j] = 1 + Math.min(solve(s, i + 1, j), solve(s, i, j - 1)); } return memo[i][j]; }}Complexity
Time
O(n^2). Each of the `n * n` possible subproblems is computed exactly once. The computation for each subproblem takes constant time.
Space
O(n^2) for the memoization table, plus O(n) for the recursion stack depth. The total space complexity is O(n^2).
Trade-offs
Pros
Significantly more efficient than brute-force, with a polynomial time complexity.
Maintains the top-down, logical structure of the recursive solution.
Cons
Requires O(n^2) space for the memoization table, which can be significant for large n.
Still has the overhead associated with recursive function calls.
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; }}class Solution {public: int minInsertions(string s) { int n = s.size(); int f[n][n]; memset(f, -1, sizeof(f)); function<int(int, int)> dfs = [&](int i, int j) -> int { if (i >= j) { return 0; } if (f[i][j] != -1) { return f[i][j]; } int ans = 1 << 30; if (s[i] == s[j]) { ans = dfs(i + 1, j - 1); } else { ans = min(dfs(i + 1, j), dfs(i, j - 1)) + 1; } return f[i][j] = ans; }; return dfs(0, n - 1); }};class Solution: def minInsertions(self, s: str) -> int: @ cache def dfs(i: int, j: int) -> int: if i >= j: return 0 if s[i] == s[j]: return dfs(i + 1, j - 1) return 1 + min(dfs(i + 1, j), dfs(i, j - 1)) return dfs(0, len(s) - 1)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.