Shortest Common Supersequence — LCS + Reconstruction for Hard DP Interviews

Problem Statement#

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of lowercase English letters

Example 1:

Input:  str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation:
  str1 = "abac" is a subsequence of "cabac" (remove c, b)  -> abac
  str2 = "cab"  is a subsequence of "cabac" (remove a, c)  -> cab
  "cabac" is the shortest such string (length 5).

Example 2:

Input:  str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output: "aaaaaaaa"
Explanation: Both strings are identical — the supersequence is the string itself.

Example 3:

Input:  str1 = "abc", str2 = "xyz"
Output: "axbycz" (or any other valid SCS of length 6)
Explanation: No characters in common — all must appear once each.

Why This Problem Matters#

Shortest Common Supersequence (SCS) is a hard-level problem that builds directly on LCS. It tests two skills simultaneously:

1. Computing the LCS using 2D DP (LC 1143 pattern)
2. Reconstructing the actual SCS string by backtracking the DP table

The connection is elegant: SCS length = len(str1) + len(str2) - LCS(str1, str2). Characters in the LCS appear once; all other characters from both strings appear separately. The reconstruction step — which characters to include and in which order — is the hard part that separates candidates who memorize formulas from those who truly understand 2D DP structure.

Google and Amazon include this problem to test DP reconstruction skills that also appear in Edit Distance path recovery, sequence alignment in bioinformatics, and diff algorithms.

The Core Insight#

Step 1: Compute the LCS length table. Use the standard LCS recurrence on a (m+1) x (n+1) DP table:

• dp[i][j] = dp[i-1][j-1] + 1 if str1[i-1] == str2[j-1]
• dp[i][j] = max(dp[i-1][j], dp[i][j-1]) otherwise

Step 2: Reconstruct the SCS by backtracking the LCS table. Start at (m, n) and move toward (0, 0):

• If str1[i-1] == str2[j-1]: the character is part of the LCS — include it once and move diagonally (i-1, j-1).
• If dp[i-1][j] > dp[i][j-1]: came from above — include str1[i-1] and move up (i-1, j).
• Otherwise: came from left — include str2[j-1] and move left (i, j-1).

After reaching row 0 or column 0, append the remaining characters from whichever string still has characters left.

Reverse the collected characters (built backward during backtracking).

Length formula: SCS_length = m + n - LCS_length

Building the DP Solution#

Step 1 — Compute LCS table:

def lcs_table(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp

Step 2 — Reconstruct SCS from LCS table:

def reconstruct(str1, str2, dp):
    i, j = len(str1), len(str2)
    result = []
    while i > 0 and j > 0:
        if str1[i-1] == str2[j-1]:
            result.append(str1[i-1])  # LCS character — include once
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            result.append(str1[i-1])  # str1 character not in LCS
            i -= 1
        else:
            result.append(str2[j-1])  # str2 character not in LCS
            j -= 1
    # Append remaining characters
    while i > 0:
        result.append(str1[i-1])
        i -= 1
    while j > 0:
        result.append(str2[j-1])
        j -= 1
    return ''.join(reversed(result))

Visual Dry Run#

Input: str1 = "abac", str2 = "cab"

LCS DP table:

LCS length = dp[4][3] = 2. LCS = "ab".

Backtracking trace (start at i=4, j=3):

Result (reversed): 'a','b','a','c','a','b' reversed = "cabac". Length 5. Correct.

Full SCS reconstruction table:

Optimized Solution#

Python#

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)
 
        # Step 1: Build full LCS DP table (needed for reconstruction)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if str1[i - 1] == str2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
 
        # Step 2: Reconstruct SCS by backtracking from (m, n) to (0, 0)
        result = []
        i, j = m, n
 
        while i > 0 and j > 0:
            if str1[i - 1] == str2[j - 1]:
                result.append(str1[i - 1])  # LCS character — include once
                i -= 1
                j -= 1
            elif dp[i - 1][j] > dp[i][j - 1]:
                result.append(str1[i - 1])  # str1-only character
                i -= 1
            else:
                result.append(str2[j - 1])  # str2-only character
                j -= 1
 
        # Append any remaining characters from str1 or str2
        while i > 0:
            result.append(str1[i - 1])
            i -= 1
        while j > 0:
            result.append(str2[j - 1])
            j -= 1
 
        return ''.join(reversed(result))

JavaScript#

var shortestCommonSupersequence = function(str1, str2) {
    const m = str1.length;
    const n = str2.length;
 
    // Build LCS DP table
    const dp = Array.from({length: m + 1}, () => new Array(n + 1).fill(0));
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (str1[i - 1] === str2[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]);
            }
        }
    }
 
    // Reconstruct SCS
    let i = m, j = n;
    const result = [];
 
    while (i > 0 && j > 0) {
        if (str1[i - 1] === str2[j - 1]) {
            result.push(str1[i - 1]);
            i--; j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            result.push(str1[i - 1]);
            i--;
        } else {
            result.push(str2[j - 1]);
            j--;
        }
    }
 
    while (i > 0) { result.push(str1[i - 1]); i--; }
    while (j > 0) { result.push(str2[j - 1]); j--; }
 
    return result.reverse().join('');
};

Complexity Analysis#

Note: Space cannot be reduced to O(n) for this problem because reconstruction requires the full 2D table.

Common Mistakes#

1. Computing SCS length only and claiming it is the answer. The problem asks for the actual SCS string, not just its length. Many candidates compute m + n - LCS_length and stop. You must reconstruct the string via backtracking.

2. Including LCS characters twice. When backtracking and both characters at str1[i-1] and str2[j-1] match, include the character once and advance both i and j. Including it from both strings doubles it in the SCS — a very common error.

3. Incorrect tie-breaking in backtracking. When dp[i-1][j] == dp[i][j-1], either direction is valid. Consistently choosing one direction (e.g., always prefer str1) prevents inconsistent results. The problem says any valid SCS is acceptable.

4. Forgetting to append remaining characters after the while loop. After the main while i > 0 and j > 0 loop, one string may still have characters remaining. Always append them: while i > 0: append str1[i-1], i-- and same for j.

5. Reversing incorrectly or not at all. Characters are collected from (m, n) back to (0, 0) — in reverse order. The result must be reversed at the end. Forgetting this produces the SCS in backward order.

Interview Tips#

• State the LCS connection explicitly: "The SCS length is m + n - LCS_length because LCS characters appear once; all others appear individually."
• Draw the DP table and show the backtracking path. Interviewers want to see that you can reason about the diagonal/up/left transitions.
• Explain the backtracking rule precisely: "On character match, include once and move diagonally. On mismatch, include the character from whichever string leads to a larger LCS value — that's the string we're 'consuming' at this step."
• Mention you cannot reduce space for this problem: "Unlike LCS length where 1D rolling works, reconstruction requires the full 2D table."
• For the length-only variant: "If only the SCS length is needed, m + n - LCS(str1, str2) with the rolling-array LCS gives O(n) space."

Follow-up Questions#

Q: What if you only need the length of the SCS? SCS_length = len(str1) + len(str2) - longestCommonSubsequence(str1, str2). Use the space-optimized rolling-array LCS (O(n) space).

Q: How does SCS relate to Edit Distance? Edit Distance (inserts + deletes only, no replacements) = m + n - 2 * LCS. SCS length = m + n - LCS. Both are derived from LCS; Edit Distance penalizes the mismatch gap from both sides.

Q: What is the SCS of 3 strings? Extend the LCS DP to 3D: dp[i][j][k] = LCS of the three prefixes. SCS length = m + n + p - (pairwise corrections). Reconstruction follows the same logic across 3 dimensions.

Q: Is the SCS unique? Not necessarily. Multiple valid SCS strings of the same minimum length may exist. The problem only asks for any one of them, which makes tie-breaking in backtracking a free choice.

Key Takeaways#

• SCS = characters from the LCS (included once) + all non-LCS characters from both strings (included separately). Length = m + n - LCS_length.
• Reconstruction backtracks the LCS table: diagonal on character match (include once), up (include str1[i-1]), left (include str2[j-1]).
• After the main loop, always append remaining characters from whichever string is not yet exhausted.
• Always reverse the collected result — backtracking goes from end to start.
• The full 2D LCS table is required for reconstruction — space cannot be compressed to 1D for this problem.
• This problem is a hard-level benchmark that combines LCS table computation with reconstruction — mastering it makes Edit Distance path recovery and sequence alignment problems trivial by comparison.