Shortest Common Supersequence

Shortest Common Supersequence

What is this problem about?

The Shortest Common Supersequence interview question asks you to find the shortest string that has both str1 and str2 as subsequences. Unlike the LCS (longest common subsequence) which removes characters, this problem builds the minimal string containing both. The SCS length = len(str1) + len(str2) - LCS_length. Reconstructing the actual string requires backtracking through the LCS DP table.

Why is this asked in interviews?

Microsoft, Meta, Amazon, Google, and Bloomberg ask this HARD string DP problem because it builds directly on LCS — a foundational dynamic programming problem — but adds the reconstruction step. Finding the SCS length is straightforward; building the actual shortest supersequence from the DP table tests candidates' ability to trace DP decisions. This models DNA sequence merging, file merge conflict resolution, and edit distance reconstruction.

Algorithmic pattern used

The pattern is LCS DP with string reconstruction. Build the standard LCS table dp[i][j] = length of LCS of str1[:i] and str2[:j]. Then reconstruct the SCS by backtracking: if str1[i-1] == str2[j-1], add that character once and move diagonally. If dp[i-1][j] > dp[i][j-1], add str1[i-1] and move up. Otherwise, add str2[j-1] and move left. After exhausting one string, append the remaining characters of the other.

Example explanation

str1 = "ace", str2 = "abcde".

LCS = "ace" (length 3).

SCS length = 3 + 5 - 3 = 5.

Reconstruction:

• a==a: add 'a'. Move to "ce", "bcde".
• dp guides: add 'b'. Move to "ce", "cde".
• c==c: add 'c'. Move to "e", "de".
• add 'd'. Move to "e", "e".
• e==e: add 'e'.

SCS: "abcde".

Common mistakes candidates make

• Computing only the SCS length without reconstructing the actual string — the hard part is backtracking.
• Incorrectly handling the backtracking direction — when str1[i-1] != str2[j-1], you must add the character from the direction of the larger dp value.
• Forgetting to append the remaining characters of the non-exhausted string after backtracking reaches one boundary.
• Reversing the reconstructed string — append characters during backtracking and reverse at the end, or build the string forward using iteration.

Interview preparation tip

For the Shortest Common Supersequence coding problem, the string dynamic programming interview pattern is the core skill. The SCS length formula (sum of both lengths minus LCS length) is the key mathematical insight. Bloomberg and Dream11 interviewers test the backtracking step — practice tracing through the DP table with a small example before coding. The SCS reconstruction is closely related to edit distance path reconstruction — master both backtracking patterns together as they use the same DP table traversal logic.