Skip to main content

1092. Shortest Common Supersequence

hard

Return the shortest string that contains both str1 and str2 as subsequences. Build the LCS table, then trace back to reconstruct a string that interleaves the two — keeping LCS chars exactly once.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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. A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.

Constraints

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

Examples

Example 1

Input
str1 = "abac", str2 = "cab"
Output
"cabac"

Explanation: str1 = "abac" is a subsequence of "cabac" because we can delete the first "c". str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac". The answer provided is the shortest such string that satisfies these properties.

Example 2

Input
str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output
"aaaaaaaa"

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Length of the answer equals len(str1) + len(str2) - LCS(str1, str2). Each LCS character is shared once instead of twice.

Hint 2

Build the standard LCS DP table dp[m+1][n+1].

Hint 3

Walk back from (m, n): if s1[i-1] == s2[j-1], append that char and decrement both indices. Else step in the direction of the larger dp value and append the corresponding char from that side.

Hint 4

Append remaining prefix of whichever string still has characters left. Reverse to get final answer.

Solution approach

Reveal approach

Two-stage. Stage 1: compute the standard LCS table dp[m+1][n+1] where dp[i][j] is the LCS length of str1[0..i-1] and str2[0..j-1]. Stage 2: reconstruct. Start at (i, j) = (m, n) and walk backward, appending characters to a result list. If str1[i-1] == str2[j-1], append that character and decrement both i and j. Otherwise compare dp[i-1][j] and dp[i][j-1]; step in the direction of the larger value, append the character from the corresponding string. When i or j reaches 0, append the remaining prefix of the other string. Reverse the result list. Final length is m + n - dp[m][n]. The choice 'when dp values are equal' affects which valid answer you return.

Complexity

Time
O(m * n)
Space
O(m * n)

Related patterns

  • dynamic-programming
  • string-dp
  • two-strings-table

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Shortest Common Supersequence and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →