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:
|
|
Example 2:
|
|
Example 3:
|
|
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]
ifs[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
|
|
|
|
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 substrings[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
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(N^2)
, because there areO(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 substrings[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]
, thendp[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).
- If
- 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++
|
|
Java
|
|
Python
|
|
Complexity
- ⏰ Time complexity:
O(N^2)
, because we fill a DP table of sizeN 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 strings
. - Compute the length of the longest common subsequence (LCS) between
s
andt
. - The answer is
len(s) - LCS(s, t)
.
Code
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(N^2)
, for filling the LCS DP table. - 🧺 Space complexity:
O(N^2)
, for the DP table.