DEV Community

Abhishek Singh
Abhishek Singh

Posted on

Minimum Operations to Make two strings Equal

The idea behind this code is that we check for the longest common subsequence(LCS) in both the strings and once we get it, we simply subtract the length of that LCS from both strings and add both the differences.
eg: str1 = "abcd" : str2 = "aed"
Here we have "ad" as LCS so in str1 we delete b,c which is 2
operations and we insert "e" in it which is another operation.
Hence total of 2+1=3 operations.
This can also be written as (str1-ad)+(str2-ad) or (str1+str2)-2*ad or (str1.len + str2.len)-2*LCS.len .

`public static int operationsCount(String s1, String s2) {

    int n=s1.length();
    int m=s2.length();
    int prev[]=new int[m+1];

    for(int ind1=1;ind1<=n;ind1++){
        int cur[]=new int[m+1];
    for(int ind2=1;ind2<=m;ind2++){
        if(s1.charAt(ind1-1)==s2.charAt(ind2-1))
            cur[ind2] = 1 + prev[ind2-1];
        else
            cur[ind2] = 0 + Math.max(prev[ind2],cur[ind2-1]);
    }
    prev= cur;
}

return (n+m)-2*prev[m];
}`
Enter fullscreen mode Exit fullscreen mode

Top comments (0)