SQUAD_SYMMETRY - Editorial

editorial
1

PROBLEM LINK:

Practice

Author: bug_hunter_1
Tester: bug_hunter_1
Editorialist: bug_hunter_1

DIFFICULTY:

MEDIUM

PREREQUISITES:

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);
}