# Edit distance variant — shortest common super-sequence

The motivation for this problem came from Steven Skiena :

8–4. The longest common subsequence (LCS) of two sequences T and P is the longest sequence L such that L is a subsequence of both T and P. The shortest common supersequence (SCS) of T and P is the smallest sequence L such that both T and P are a subsequence of L.

1. Give efficient algorithms to find the LCS and SCS of two given sequences

To pick an example : Input: str1 = “abac”, str2 = “cab”
Output: “cabac”

The approach to this problem would be :

Figure out the longest common subsequence between str1 and str2.

Then iterate the strings and the lcs — if a character does not match — add it to the string. Figure out the final result and return it.

`public String shortestCommonSupersequence(String str1, String str2) {        String lcs = getLcs(str1, str2);        int count1 = 0, count2 = 0;        String result = "";        for(int i = 0; i < lcs.length(); i++) {            while(count1 < str1.length() && str1.charAt(count1) != lcs.charAt(i)) {                result += str1.charAt(count1++);            }            while(count2 < str2.length() && str2.charAt(count2) != lcs.charAt(i)) {                result += str2.charAt(count2++);            }            result += lcs.charAt(i);            count1++;            count2++;        }        return result + str1.substring(count1) + str2.substring(count2);    }        String getLcs(String str1, String str2) {        String[][] dp = new String[str1.length() +1][str2.length()+1];        for(int i = 0; i < dp.length; i++)        Arrays.fill(dp[i], "");        for(int i = 1; i <= str1.length(); i++) {            for(int j = 1; j <= str2.length(); j++) {                char chI = str1.charAt(i-1);                char chJ = str2.charAt(j-1);                if(chI == chJ) {                    dp[i][j] = dp[i-1][j-1] + chI;                } else {                    dp[i][j] = dp[i-1][j].length() > dp[i][j-1].length() ?                         dp[i-1][j] : dp[i][j-1];                }            }        }        return dp[str1.length()][str2.length()];    }`

--

--

I’m a software engineer with a strong interest in algorithms. I love solving puzzles and love the aha moment of arriving at a solution after hours of struggle.