Shortest Common Supersequence - Video Solutions

Problem Overview: Given two strings str1 and str2, construct the shortest string that contains both as subsequences. Characters must keep their original order from each string, but you can interleave them.

Approach 1: Dynamic Programming with LCS Reconstruction (O(m*n) time, O(m*n) space)

The shortest common supersequence (SCS) is closely related to the longest common subsequence (LCS). First compute the LCS table using classic dynamic programming. The LCS captures characters shared by both strings in order. Once the DP table is built, reconstruct the supersequence by walking backward from dp[m][n]. When characters match, append it once and move diagonally. When they differ, move toward the larger DP value and append the corresponding character. This guarantees the result keeps both strings as subsequences while avoiding duplicate shared characters.

This approach works because the optimal SCS length equals m + n - LCS. The DP table gives the structure needed to merge both strings efficiently. Time complexity is O(m*n) for building the LCS table, and reconstruction takes O(m+n). Space complexity is O(m*n) for the DP matrix.

Approach 2: Iterative Greedy Merge Using LCS (O(m*n) time, O(m*n) space)

Another implementation computes the LCS first, then performs a greedy merge of both strings while iterating through the LCS characters. Maintain two pointers for str1 and str2. For each LCS character, append all characters from str1 until reaching that character, then append all characters from str2 until reaching it. Finally append the shared LCS character once and advance both pointers. After processing all LCS characters, append remaining characters from both strings.

This method emphasizes string merging rather than backtracking through the DP table. It is often easier to implement when the LCS sequence is already available. The time complexity remains O(m*n) for computing the LCS and O(m+n) for the merge. Space complexity is O(m*n) for the DP used to compute LCS.

The problem heavily relies on understanding subsequence relationships in string problems and applying optimal substructure from dynamic programming.

Recommended for interviews: The dynamic programming LCS approach is the expected solution. Interviewers want to see that you recognize the SCS–LCS relationship and reconstruct the answer from the DP table. The greedy merge approach is a clean follow-up implementation once the LCS is known.