Practice

Author: bug_hunter_1
Tester: bug_hunter_1
Editorialist: bug_hunter_1

MEDIUM

Math Strings

# PROBLEM:

Find the minimum number of steps, to insert (any) chars in a string such that the resultant string becomes pallindrome

# QUICK EXPLANATION:

String length - the length of the longest common subsequence

# EXPLANATION:

``````Basically your answer would be [Assuming that you know how to find longest common subsequence] -->
s.length() - lcs(s1, reverse(s1), n , m);
where n == s1.length;
m = s1.reverse().length();

The number of chars that would have to be inserted ( right or left we don't care). So we make a string copy of the original string and the reverse it. Apply lcs on both and then return the answer.

In case you need a refreasher for the lcs part we make the dp table using the following decisions :

WE HAVE 2 DECISION, EITHER ADD A CHARACTER ON THE LEFT SIDE(i pointer) OR ADD A CHARCTER on the RIGHT SIDE(j pointer)
ADDING ONE CHAR ON THE LEFT AND INCREMENT THE DECISION+1 AND calling recursively ON i+1 and j
ADDING ONE CHAR ON THE RIGHT AND INCREMENT THE DECISION+1 AND calling recursively ON i and j+1
SAVING THE MINIMUM OF THE 2 DECISION ON dp[i][j]
RETURNING THE MINIMUM DECISION THAT WE GOT
``````

# SOLUTIONS:

Setter's Solution
``````#include <bits/stdc++.h>
using namespace std;

int fun(string str1, string str2)
{
int n=str1.length(), m=str2.length();
int dp[n+1][m+1];
for(int i=0; i<=n; i++)
{
for(int j=0; j<=m; j++)
{
if(i==0 || j==0)
dp[i][j]=0;

else if(str1[i-1]==str2[j-1])
dp[i][j]=1+dp[i-1][j-1];

else
dp[i][j]=max(dp[i][j-1], dp[i-1][j]);

}
}
return dp[n][m];
}

int minInsertions(string str) {
string str2=str;
reverse(str2.begin(), str2.end());
return str.length()-fun(str, str2);
}

int main(void) {
string s;
cin >> s;
cout << minInsertions(s);
}
``````