LEASTDELSTR -Editorial

editorial
1

PROBLEM LINK:

Practice

Author: Kunal Demla
Editorialist: Kunal Demla

DIFFICULTY:

Hard

PREREQUISITES:

Dynamic Programing

PROBLEM:

Given 2 strings, find the minimum no. of deletions required to make them equal.

QUICK EXPLANATION:

Find the LCS, Ans= s1.length - LCS + s2.length - LCS.

EXPLANATION:

We break the problem into smaller parts, essentially considering only parts of the words, and al finding the longest common subsequence we can get in the strings. Then we substract the same from their lengths to find the no. of deletions required.

ALTERNATE EXPLANATION:

Instead the No. of deletions can directly be stored.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
using namespace std;
#define ll long long int

void solve()
{
    ll n,m,x,y,i,j,k;
    string s1,s2;
    cin>>s1>>s2;
    vector<vector<int>> dp(s1.length()+1, vector<int> (s2.length()+1,0));
    for(i=1;i<=s1.length();i++){
        for(j=1;j<=s2.length();j++){
            if(s1[i-1]==s2[j-1]){
                dp[i][j]=1+max(dp[i-1][j],dp[i][j-1]);
            }
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    cout<<s2.length()+s1.length()-dp[i-1][j-1]-dp[i-1][j-1];
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int t=1;
cin>>t;
int n=t;
while(t--)
{
    solve();
    cout<<"\n";
}

cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" secs"<<endl;
return 0;
}