Shortest Common Super-sequence

Shortest Common Super-sequence (SCS)

A shortest common super-sequence of s1 and s2 is the shortest string that contains both as subsequences (not necessarily contiguous) — it works because every character the two strings share in order (their Longest Common Subsequence, LCS) needs to appear only once in the super-sequence, while every other character must appear once for each string it belongs to. So SCS length = |s1| + |s2| − LCS(s1, s2): you pay for both strings in full, then get a refund equal to the overlap.

Recognize the pattern

• Prompt asks for the shortest string such that two (or more) given strings are subsequences of it — not substrings.
• Output must "contain both" while being minimal — hints at merging with maximum shared structure.
• Follow-up variants: "print the actual super-sequence", "minimum insertions/deletions to make s1 == s2", "merge two strings, keeping relative order of both" — all are LCS in disguise.

Brute force → optimal

Brute force: recursively try, for every prefix pair (i, j), either matching equal characters or branching on which string contributes the next character — this revisits the same (i, j) subproblem exponentially many times. Cost: O(2^(m+n)) time, O(m+n) recursion stack.

Optimal: memoize on (i, j) — there are only (m+1)(n+1) distinct subproblems, each doing O(1) work beyond its recursive calls, since it's exactly the LCS recurrence. Compute LCS length via DP, then derive SCS length in O(1), or walk the LCS table backward to build the actual string.

Complexity, derived

Let m = |s1|, n = |s2|. The DP table has (m+1) × (n+1) cells; each cell does O(1) work (one comparison, one addition, one max) ⇒ time O(m·n). The table itself is (m+1)(n+1) integers ⇒ space O(m·n), reducible to O(min(m,n)) with rolling rows if you only need the length (not the reconstruction path). Reconstruction is a single backward walk over at most m+n steps, O(m+n) extra time.

Worked example

s1 = "abcf", s2 = "bdcf". Build the LCS table, dp[i][j] = LCS length of s1[0..i) and s2[0..j):

LCS length = 3 ("bcf") ⇒ SCS length = 4 + 4 − 3 = 5.

Reconstruction, walking backward from (i=4, j=4):

1. s1[3]='f' == s2[3]='f' → emit f, move to (3,3)
2. s1[2]='c' == s2[2]='c' → emit c, move to (2,2)
3. s1[1]='b' != s2[1]='d'; dp[1][2]=0 ≤ dp[2][1]=1 → emit d (from s2), move to (2,1)
4. s1[1]='b' == s2[0]='b' → emit b, move to (1,0)
5. j=0: flush remaining s1[0..1) = "a"

Emitted order f,c,d,b,a, reversed → "abdcf", length 5. Matches.

Java

class SCS {
    // Returns {length, actual SCS string}
    static Object[] shortestCommonSupersequence(String s1, String s2) {
        int m = s1.length(), n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; 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 - 1][j], dp[i][j - 1]);
                }
            }
        }
        int lcsLen = dp[m][n];
        int scsLen = m + n - lcsLen;

        StringBuilder sb = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                sb.append(s1.charAt(i - 1)); i--; j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                sb.append(s1.charAt(i - 1)); i--;
            } else {
                sb.append(s2.charAt(j - 1)); j--;
            }
        }
        while (i > 0) { sb.append(s1.charAt(i - 1)); i--; }
        while (j > 0) { sb.append(s2.charAt(j - 1)); j--; }
        sb.reverse();
        return new Object[]{scsLen, sb.toString()};
    }
}

Pitfalls

• Using the substring DP (like edit-distance-with-only-insert) instead of the subsequence LCS-based recurrence — SCS characters need not be contiguous in either input.
• Off-by-one in the backward walk: comparing dp[i-1][j] vs dp[i][j-1] the wrong way silently produces a valid-length but character-wrong super-sequence, or loses the tie-break that keeps the result deterministic.
• Forgetting to flush the remaining prefix of whichever string still has characters left after the while loop ends (only one of i,j hits 0 first).
• Space-optimizing the LCS length computation (rolling array) but then still trying to reconstruct the string from it — reconstruction needs the full table.

When to use / when not

Use the LCS-based DP whenever the ask is literally SCS, or any of its restatements: "minimum insertions to make s1 a subsequence of a merge", "minimum operations to make two strings identical using only insertions" (answer = m + n − 2·LCS), or "print the shortest supersequence". Trade-off vs. brute-force recursion with memoization (top-down): functionally identical complexity, but bottom-up tabulation avoids recursion-stack overhead and is easier to space-optimize; recursive memoization is easier to write correctly under time pressure and naturally skips unreachable states. Do not reach for this LCS-based SCS when the requirement is about the shortest string containing both inputs as substrings (contiguous) — that's the classic "shortest common superstring" problem, solved by finding the maximum prefix-suffix overlap between the two strings (e.g. via KMP failure-function or Z-function overlap matching) and splicing on the non-overlapping remainder, not by LCS.

Takeaways

• SCS length = |s1| + |s2| − LCS(s1, s2) — the whole problem reduces to computing LCS.
• The DP table cell recurrence is exactly LCS's: diagonal +1 on match, else carry the max of top/left (no +1 on a mismatch).
• Building the actual string needs a backward walk over the full O(mn) table, not just the length.
• The SCS length is unique, but the SCS string need not be — different tie-breaks in the backward walk (which neighbor to follow on a mismatch) produce different, equally-short supersequences.

Recall: Why does SCS length equal |s1| + |s2| − LCS(s1, s2) rather than requiring a separate DP formulation?

Sources: CLRS (LCS foundations); GeeksforGeeks & LeetCode problem discussions on Shortest Common Supersequence; standard DP-on-two-strings pattern as taught in competitive programming references (cp-algorithms).