BEAUTARR - Editorial - TWZT20TS

editorial
, ,
1

PROBLEM LINK:

Practice

Author: Piyush
Tester: Vishal Sharma
Editorialist: Piyush

DIFFICULTY:

Easy

PREREQUISITES:

Dynamic Programming

PROBLEM:

There will be two strings given. We need to find out the Longest Common Subsequence given that we have to make exactly K operations, where in each operation, any alphabet can be changed to any of the 26 alphabets.

QUICK EXPLANATION:

First of all, lets clear the exactly K operations part. Since in an operation, an alphabet can be changed to any other alphabet, you can change any given alphabet to itself just to exhaust the operations. So exactly K converts to at most K.

This is a simple dynamic programming question, where you can define a state according to indices on each of the strings and the number of operations which can be performed currently, making it a 3-D DP;

dp[i][j][k] = Length of LCS for s1 and s2 starting from i^{th} index in s1 and j^{th} index in s2 with k operations remaining.

So our solution would be dp[0][0][K].

The recurrence is defined by:

dp[i][j][k] = \begin{cases} 1 + dp[i+1][j+1][k] & \quad \text{if } \text{ s1[i] == s[j]}\\ max(dp[i+1][j][k], dp[i][j+1][k], k>0?dp[i+1][j+1][k-1]:0) & \quad \text{otherwise } \end{cases}

EXPLANATION:

First of all let us try to build a recursive solution for the same. Let us assume a function f(i,j,k) which will return us the LCS of strings s1 and s2 starting from i^{th} index in s1 and j^{th} index in s2 with K operations remaining.

Now if we have this function ready, we can simply call f(0,0,K) to get our answer. Now let’s look into the cases which can arise while we are trying to implement the function.

While we are at i^{th} index in s1 and j^{th} index in s2, two major cases will arise:

  1. s1[i] == s2[j]
    Now, if this happens, we will include this character into our LCS length, and move on to the next indices.
    So we have to return 1 + f(i+1,j+1,k).
    We did not change any character and hence k remains unaffected.

  2. s1[i] \neq s2[j]
    In this case, we have three options in hand:

    a. Ignore s1[i] and move on to next index in s1.

    In this case, the answer will be f(i+1,j,k).

    b. Ignore s2[j] and move on to next index in s2.

     In this case, the answer will be f(i,j+1,k).

    c. If we have at least one operation remaining, change s1[i] to match s[j].

     Here we are using up one operation and getting a increment in total LCS, hence the answer will be 1 + f(i+1,j+1,k-1).

    Out of all the three options, we will chose the one with maximum LCS length.
    Hence we return maximum of all the above.

Also, we can observe, that we will have some repeated states while using recursion. Hence we can store the answer of these states in a 3D array and return the value if it is already precomputed. This is the top-down DP solution.

Time Complexity: O(N * M * K)

Space Complexity: O(N * M * K)

ALTERNATE EXPLANATION:

Instead of using top-down approach, we can also use bottom-up approach where we will not call the any function recursively, but will directly fill the dp array as is explained in the solution.

SOLUTION:

Solution 
#include<bits/stdc++.h>
using namespace std;


int main() {
int n,m,k;
cin>>n>>m>>k;
string s1,s2;
cin>>s1>>s2;

// Initialise the dp array
int dp[n+1][m+1][k+1] = {};

for(int t=0;t<=k;t++) {
    for(int i=n;i>=0;i--) {
    for(int j=m;j>=0;j--) {
        //Base case
        if(i==n || j==m) {
        dp[i][j][t] = 0;
        } 
        
        //Case 1
        else if(s1[i] == s2[j]) {
        dp[i][j][t] = dp[i+1][j+1][t] + 1;
        } 
        
        //Case 2
        else {
        dp[i][j][t] = max(dp[i+1][j][t], dp[i][j+1][t]);
        if(t>0) {
            dp[i][j][t] = max(dp[i][j][t], 1+dp[i+1][j+1][t-1]);
        }
        }
    }
    }
}

cout<<dp[0][0][k]<<endl;



return 0;
}
1 Like