Shortest Common Supersequence

Hard25–30 min

Topics

Dynamic ProgrammingString

Companies

AmazonGoogleAdobe

Given two strings str1 and str2, find the shortest possible string that contains both of them as subsequences (characters in the right relative order, not necessarily adjacent). If several shortest strings work, any one of them is accepted. Whatever gets merged for free has to be a character both strings already agree on, in the same relative order — in other words, exactly the longest common subsequence. Everything outside that shared backbone still needs to appear once, taken verbatim from whichever original string it came from. So the shape of the answer falls out of the LCS length table almost immediately: walk that table from the end of both strings back to the start, and at every step either the two current characters already match (keep one copy, move past both) or they don't (copy whichever character still has more shared potential ahead of it, according to the table, and move past just that one side). What's left over once one string runs out gets tacked on unchanged.

Test Case 1:

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

Output:"cabac"

Explanation:Length-2 LCS "ab" is kept once; the leftover 'c' from str1 and the leftover 'c' from str2 collapse into a single shared 'c', giving the 5-character result "cabac" (both "abac" and "cab" read off it as subsequences).

Test Case 2:

Input:str1 = "abc", str2 = "def"

Output:"defabc"

Explanation:No character is shared, so nothing can be merged — the shortest supersequence is just one string glued after the other, 6 characters long either way round (only the order changes which specific string comes first).

Test Case 3:

Input:str1 = "abc", str2 = "abc"

Output:"abc"

Explanation:Identical strings are already a common supersequence of each other — nothing to add.

Constraints

◆0 ≤ str1.length, str2.length ≤ 10
◆str1 and str2 consist of lowercase English letters
◆the returned string's length never exceeds str1.length + str2.length

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Recursive Backtrack After Building the LCS Table

Brute

A shortest supersequence keeps every character of the longest common subsequence exactly once, and fills in everything around it straight from whichever original string that character came from. So the plan splits in two: first fill an LCS length table for str1 and str2 the usual way, then walk it backwards from the bottom-right corner, letting the table tell you at each step whether you're standing on a shared character (take it once, move diagonally) or a character that only one side owns (copy it from whichever side has more matching potential still ahead, per the table, and move over just that one side). Recursing through that walk-back is simple to write but pays for the call stack and string concatenation at every step.

TimeO(n·m)

SpaceO(n·m)

Java

Try it out

class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int n = str1.length(), m = str2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1.charAt(i - 1) == str2.charAt(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]);
                }
            }
        }
        return backtrack(dp, str1, str2, n, m);
    }
    private String backtrack(int[][] dp, String str1, String str2, int i, int j) {
        if (i == 0) return str2.substring(0, j);
        if (j == 0) return str1.substring(0, i);
        if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
            return backtrack(dp, str1, str2, i - 1, j - 1) + str1.charAt(i - 1);
        }
        if (dp[i - 1][j] >= dp[i][j - 1]) {
            return backtrack(dp, str1, str2, i - 1, j) + str1.charAt(i - 1);
        }
        return backtrack(dp, str1, str2, i, j - 1) + str2.charAt(j - 1);
    }
}

Iterative Backtrack After Building the LCS Table

Optimal

Exactly the same table and the same walk-back rule as the recursive version, just driven by a plain loop instead of a call stack: keep two pointers into str1 and str2, step them backward according to the table, and append every character you visit to a buffer. Because the walk runs from the end of both strings toward the start, the buffer fills in reverse order, so a single reversal at the very end puts it right — no recursion overhead, no repeated string concatenation.