- Case 1:The first and last characters are equal. In this case, the minimum number of characters to insert depends on the sub-string between the first and last characters.
- For example consider the string “abca”, the value depends on the sub-string “bc”
- case 2:The first and last characters are not equal. In this case, we have to make the first and last characters equal to make it a palindrome. We can do this in two ways. Either we can insert a new character before the first character, or next to the last character.
- For example consider “gcc”, to make first and last characters equal, we can insert a “c” first or insert a “g” last. It either becomes “cgcc” or “gccg”. since “gccg” is minimal way of making a palindrome, We just need to insert 1 character.
MCI(str) = MCI( str[1:n-2] ) if str[0] = str[n-1]
= Min( MCI(str[0:n-2]), MCI(str[1:n-1]))+1 otherwise
A naive recursive implementation is straight forward. To implement dynamic programming solution, we create a a two dimensional table of size n*n.
table[i][j] indicates MCI of the sub-string str[i:j] the table is calculated using the following rules.
table[i][i] is always 0 because a single character is a palindrome.
table[i][j] = table[i+1][j-1] if str[i] = str[j]
= Min(table[i+1][j], table[i,j-1])+1 otherwise
We construct this table in bottom up manner i.e solve the smaller problems first and use their result to solve bigger problems. Finally table[0][n-1] contains the required value.
Below is the dynamic programming implementation in C++.
#include <iostream> | |
#include <string> | |
#include <vector> | |
using namespace std; | |
int getMinInsertChars(string& str) | |
{ | |
int n = str.size(); | |
if( n == 0 ) | |
return 0; | |
vector< vector<int> > table(n, vector<int>(n)); | |
int i,j; | |
for( i = n-2; i >= 0; i-- ) | |
{ | |
for( j = i+1; j < n; j++ ) | |
{ | |
if( str[i] == str[j] ) //if first and last letters are equal | |
{ | |
//if there are 1 or 0 chars in between; no need to insert | |
//otherwise it's same as that of substring str[i+1:j-1] | |
if( j-i > 2 ) | |
table[i][j] = table[i+1][j-1]; | |
} | |
else | |
{ | |
table[i][j] = 1; | |
if( j-i > 1 ) | |
table[i][j] += min(table[i][j-1], table[i+1][j]); | |
} | |
} | |
} | |
return table[0][n-1]; | |
} | |
int main() | |
{ | |
int t; | |
cin >> t; | |
while( t-- ) | |
{ | |
string str; | |
cin >> str; | |
cout << getMinInsertChars(str) << endl; | |
} | |
return 0; | |
} |