Shortest Common Supersequence

How it works

Storing full strings in the DP table is memory-intensive. A more space-efficient approach stores only the lengths, then reconstructs the string by tracing backward through the table.

This is the standard approach for the problem: compute the DP table of lengths bottom-up, then trace from (n, m) back to (0, 0), building the result string in reverse.

Steps

1. Create a 2D table dp of size (n+1) x (m+1) to store lengths.
2. Fill base cases: dp[0][j] = j and dp[i][0] = i.
3. Fill the table:
   • If str1[i-1] == str2[j-1], set dp[i][j] = 1 + dp[i-1][j-1].
   • Otherwise, set dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]).
4. Trace back from (n, m):
   • If characters match, include it and move diagonally.
   • Otherwise, follow the smaller value (up or left) and include that character.
5. Append remaining characters from either string.
6. Reverse the result and return.

Complexity

• Time complexity: O(n * m)
• Space complexity: O(n * m)

Where n and m are the lengths of the strings str1 and str2 respectively.

Things to watch for

Confusing SCS with LCS

The Shortest Common Supersequence is related to but different from the Longest Common Subsequence. The SCS length equals len(str1) + len(str2) - LCS_length. Some solutions incorrectly try to directly apply LCS logic without understanding that SCS requires including all characters from both strings, not just the common ones.

Incorrect Traceback Direction

When reconstructing the SCS from the DP table, you must trace backward from (n, m) to (0, 0) and then reverse the result. A common mistake is tracing forward, which produces a different (incorrect) supersequence. The direction of traceback must match the direction used to fill the DP table.

Missing Characters After Traceback Loop

After the main traceback loop terminates (when either i or j reaches 0), there may still be remaining characters in one of the strings. Forgetting to append these remaining characters results in an incomplete supersequence that does not contain one of the input strings as a subsequence.

Inefficient String Concatenation

Building the result string by repeated concatenation in languages like Java or Python can lead to O(n _ m _ (n + m)) time complexity due to string immutability. Use a StringBuilder, list, or similar mutable structure and reverse at the end for optimal performance.

Off-by-One Errors in DP Indices

The DP table has dimensions (n+1) x (m+1) where indices 0 represent empty prefixes. When accessing characters, dp[i][j] corresponds to str1[i-1] and str2[j-1]. Mixing up 0-indexed string access with 1-indexed DP access causes incorrect character comparisons and wrong results.

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        n, m = len(str1), len(str2)
        dp = [[0] * (m + 1) for _ in range(n + 1)]

        for i in range(n + 1):
            for j in range(m + 1):
                if i == 0:
                    dp[i][j] = j
                elif j == 0:
                    dp[i][j] = i
                elif str1[i - 1] == str2[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1])

        res = []
        i, j = n, m
        while i > 0 and j > 0:
            if str1[i - 1] == str2[j - 1]:
                res.append(str1[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] < dp[i][j - 1]:
                res.append(str1[i - 1])
                i -= 1
            else:
                res.append(str2[j - 1])
                j -= 1

        while i > 0:
            res.append(str1[i - 1])
            i -= 1

        while j > 0:
            res.append(str2[j - 1])
            j -= 1

        return ''.join(reversed(res))

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        int n = str1.size(), m = str2.size();
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (i == 0) {
                    dp[i][j] = j;
                } else if (j == 0) {
                    dp[i][j] = i;
                } else if (str1[i - 1] == str2[j - 1]) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        string res;
        int i = n, j = m;
        while (i > 0 && j > 0) {
            if (str1[i - 1] == str2[j - 1]) {
                res.push_back(str1[i - 1]);
                i--;
                j--;
            } else if (dp[i - 1][j] < dp[i][j - 1]) {
                res.push_back(str1[i - 1]);
                i--;
            } else {
                res.push_back(str2[j - 1]);
                j--;
            }
        }

        while (i > 0) {
            res.push_back(str1[i - 1]);
            i--;
        }

        while (j > 0) {
            res.push_back(str2[j - 1]);
            j--;
        }

        reverse(res.begin(), res.end());
        return res;
    }
};