Shortest Common Supersequence

JavaView on GFG

Time: O(n*m)

Space: O(n*m)

Intuition

Build SCS from LCS DP table. LCS characters appear once; non-LCS characters from both strings each appear once.

Algorithm

1Build LCS DP table. Trace from (m,n) to (0,0).
2If s1[i]==s2[j]: take char, go diagonal. If from top: take s2[j]. If from left: take s1[i].
3Append remaining chars. Reverse.

Common Pitfalls

•Trace DP table carefully. Characters not in LCS must still appear in SCS.

Shortest Common Supersequence.java

Java

// Approach: Find LCS, then merge both strings including LCS characters only once.
// Total length = m + n - LCS length.
// Time: O(n*m) Space: O(n*m)
class Solution {
    public static int minSuperSeq(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();

        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
        
        int result = n + m - dp[n][m];// finally simplified

        return result;
    }
}

Was this solution helpful?