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