DSA
Minimum Insertion Steps to Make a String Palindrome
Covers: Recursion, Memoized DP. Optimal — Time O(n^2), Space O(n).
Practice Link
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.
Intiution#
-
In order to minimize the insertions, we need to find the length of the longest palindromic component or in other words, the longest palindromic subsequence.
-
Minimum Insertion required = n(length of the string) - length of longest palindromic subsequence.
Recursion#
Reverse the string and compute the LCS of s and its reverse — that LCS is the longest palindromic subsequence (LPS). The minimum insertions needed is n - LPS, since characters outside the LPS must each be mirrored by an insertion. Without caching, the LCS recursion has exponential time due to overlapping sub-problems.
class Solution {
public:
string reverse(string s)
{
string temp="";
for(char c: s)
{
temp = c + temp;
}
return temp;
}
int lcs(string s1, string s2, int m , int n)
{
if(m==0 || n==0)
return 0;
if(s1[m-1] == s2[n-1])
return 1 + lcs(s1,s2,m-1,n-1);
return max(lcs(s1,s2,m-1,n), lcs(s1,s2,m,n-1));
}
int longestPalindromeSubseq(string s) {
string str = reverse(s);
int lcsLength = lcs(s, str, s.length(), str.length());
return s.length()-lcsLength;
}
};
O(2^n) -> TLE (Overlapping subproblems)
Memoized DP#
Cache the LCS of prefix pairs (m, n) in a 2D memo table. Each of the (n+1)^2 states is computed once, reducing time to O(n^2). The final answer is n - lcsLength.
class Solution {
public:
string reverse(string s)
{
string temp="";
for(char c: s)
{
temp = c + temp;
}
return temp;
}
int lcs(string s1, string s2, int m , int n, vector<vector<int>> &memo)
{
if(m==0 || n==0)
return 0;
if(memo[m][n] != -1)
return memo[m][n];
if(s1[m-1] == s2[n-1])
memo[m][n] = 1 + lcs(s1,s2,m-1,n-1, memo);
else
memo[m][n] = max(lcs(s1,s2,m-1,n, memo), lcs(s1,s2,m,n-1, memo));
return memo[m][n];
}
int longestPalindromeSubseq(string s) {
int n = s.length();
string str = reverse(s);
vector<vector<int>> memo(n+1, vector<int>(n+1, -1));
int lcsLength = lcs(s, str, n, n, memo);
return n - lcsLength;
}
};
Time Complexity: O(n^2) --> Still gives TLE
Space Compelexity: O(n^2) + O(n) -> recursive stack
Tabulation#
Fill the LCS table between s and its reverse bottom-up. Each row depends only on the previous row, so the fill order is straightforward. The iterative pass removes the recursion stack, keeping O(n^2) time and space. Subtract dp[n][n] from n for the final answer.
class Solution {
public:
string reverse(string s)
{
string temp="";
for(char c: s)
{
temp = c + temp;
}
return temp;
}
int lcs(string s1, string s2)
{
int n = s1.length();
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(s1[i-1] == s2[j-1])
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[n][n];
}
int minInsertions(string s) {
int n = s.length();
string str = reverse(s);
int lcsLength = lcs(s,str);
return n - lcsLength;
}
};
Time Complexity: O(n^2)
Space Compelexity: O(n^2)
Space Optimized#
Replace the full 2D LCS table with two 1D arrays (prev and curr) of length n+1, swapping after each character. Space drops from O(n^2) to O(n) while time stays O(n^2).
class Solution {
public:
string reverse(string s)
{
string temp="";
for(char c: s)
{
temp = c + temp;
}
return temp;
}
int lcs(string s1, string s2)
{
int n = s1.length();
vector<int> prev(n+1, 0);
vector<int> curr(n+1, 0);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(s1[i-1] == s2[j-1])
curr[j] = 1 + prev[j-1];
else
curr[j] = max(prev[j], curr[j-1]);
}
prev = curr;
}
return curr[n];
}
int minInsertions(string s) {
int n = s.length();
string str = reverse(s);
int lcsLength = lcs(s,str);
return n - lcsLength;
}
};
Time Complexity: O(n^2)
Space Complexity: O(n)