Problem Statement
Given a string s, find the minimum number of insertions needed to make it a palindrome. A palindrome is a sequence that reads the same backward as forward. You can insert characters at any position in the string.
Examples
Example 1:
Input: s = "abcaa"
Output: 2
Explanation: Insert 2 characters "c", and "b" to make "abcacba", which is a palindrome.Example 2:
Input: s = "ba"
Output: 1
Explanation: Insert "a" at the beginning to make "aba", which is a palindrome.Different Approaches
1️⃣ Tabulation
Understanding:
We need to find the minimum insertions required to make a string palindrome. Let us keep the “minimum” criteria aside and think, how can we make any given string palindrome by inserting characters.
The easiest way is to add the reverse of the string at the back of the original string as shown below. This will make any string palindrome.
Here the number of characters inserted will be equal to n (length of the string). This is the maximum number of characters we can insert to make strings palindrome. The problem states us to find the minimum of insertions. Let us try to figure it out:
- To minimize the insertions, we will first try to refrain from adding those characters again which are already making the given string palindrome. For the given example, “aaa”, “aba”,”aca”, any of these are themselves palindromic components of the string. We can take any of them( as all are of equal length) and keep them intact. (let’s say “aaa”).
- Now, there are two characters(‘b’ and ‘c’) remaining which prevent the string from being a palindrome. We can reverse their order and add them to the string to make the entire string palindrome.
- We can do this by taking some other components (like “aca”) as well.
- 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.
Approach:
- We are given a string (say s), store its length as n.
- Find the length of the longest palindromic subsequence ( say k) as discussed Longest Common Subsequence
- Return (n-k) as answer.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution{
private:
/* Function to calculate the length
of the Longest Common Subsequence*/
int lcs(string s1, string s2) {
int n = s1.size();
int m = s2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, -1));
// Initialize the first row and first column to 0
for (int i = 0; i <= n; i++) {
dp[i][0] = 0;
}
for (int i = 0; i <= m; i++) {
dp[0][i] = 0;
}
for (int ind1 = 1; ind1 <= n; ind1++) {
for (int ind2 = 1; ind2 <= m; ind2++) {
if (s1[ind1 - 1] == s2[ind2 - 1])
dp[ind1][ind2] = 1 + dp[ind1 - 1][ind2 - 1];
else
dp[ind1][ind2] = max(dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]);
}
}
//Return the result
return dp[n][m];
}
/* Function to calculate the length of
the Longest Palindromic Subsequence*/
int longestPalindromeSubsequence(string s) {
string t = s;
reverse(s.begin(), s.end());
return lcs(s, t);
}
public:
/* Function to calculate the minimum insertions
required to make a string palindrome*/
int minInsertion(string s) {
int n = s.size();
int k = longestPalindromeSubsequence(s);
/* The minimum insertions required is the
difference between the string length and
its longest palindromic subsequence length*/
return n - k;
}
};
int main() {
string s = "abcaa";
//Create an instance of Solution class
Solution sol;
// Call minInsertion function and print the result
cout << "The Minimum insertions required to make string palindrome: " << sol.minInsertion(s);
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N*N), Where N is the length of the given string. As two nested loops are used to solve the problem. - Space Complexity:
O(N*N), We are using an external array of size (N*N).
2️⃣ Space Optimization
If we observe the relations obtained in tabultaion approach, dp[ind1 - 1][ind2], dp[ind1][ind2 - 1]. We are using just two rows, dp[ind1-1][ ], dp[ind][ ], in order to calculate the present row.
So we are not required to contain an entire array, we can simply have two rows 'prev' and 'cur' where prev corresponds to dp[ind-1] and cur to dp[ind].
After declaring 'prev' and 'cur', replace dp[ind-1] to prev and dp[ind] with cur in the tabulation code. Following the same logic of tabulation, we will calculate cur[ind] in each iteration and after the inner loop executes, we will set prev = cur, so that the cur row can serve as prev for the next index.
After end of the execution, return prev[n] (n is the length of the string), as our answer, as it will hold the cumulative result of the overall calculation.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution{
private:
/* Function to calculate the length
of the Longest Common Subsequence*/
int lcs(string s1, string s2) {
int n = s1.size();
int m = s2.size();
/* Create two arrays to store the
previous and current rows of DP values*/
vector<int> prev(m + 1, 0), cur(m + 1, 0);
/* Base Case is covered as we have
initialized the prev and cur to 0.*/
for (int ind1 = 1; ind1 <= n; ind1++) {
for (int ind2 = 1; ind2 <= m; ind2++) {
if (s1[ind1 - 1] == s2[ind2 - 1])
cur[ind2] = 1 + prev[ind2 - 1];
else
cur[ind2] = max(prev[ind2], cur[ind2 - 1]);
}
// Update the prev array with current values
prev = cur;
}
// The value at prev[m] contains length of LCS
return prev[m];
}
/* Function to calculate the length of
the Longest Palindromic Subsequence*/
int longestPalindromeSubsequence(string s) {
string t = s;
reverse(s.begin(), s.end());
return lcs(s, t);
}
public:
/* Function to calculate the minimum insertions
required to make a string palindrome*/
int minInsertion(string s) {
int n = s.size();
int k = longestPalindromeSubsequence(s);
/* The minimum insertions required is the
difference between the string length and
its longest palindromic subsequence length*/
return n - k;
}
};
int main() {
string s = "abcaa";
//Create an instance of Solution class
Solution sol;
// Call minInsertion function and print the result
cout << "The Minimum insertions required to make string palindrome: " << sol.minInsertion(s);
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N*N), Where N is the length of the given string. As two nested loops are used to solve the problem. - Space Complexity:
O(N), We are using an external array of size ‘N+1’ to store only two rows.