# 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.**

**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()];

}