1092. Shortest Common Supersequence - Leetcode Solution

Code Implementation

class Solution:
    def shortestCommonSupersequence(self, str1: str, str2: str) -> str:
        m, n = len(str1), len(str2)
        # Compute LCS DP table
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(m):
            for j in range(n):
                if str1[i] == str2[j]:
                    dp[i+1][j+1] = dp[i][j] + 1
                else:
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
        # Build SCS from DP table
        res = []
        i, j = m, n
        while i > 0 and j > 0:
            if str1[i-1] == str2[j-1]:
                res.append(str1[i-1])
                i -= 1
                j -= 1
            elif dp[i-1][j] >= dp[i][j-1]:
                res.append(str1[i-1])
                i -= 1
            else:
                res.append(str2[j-1])
                j -= 1
        while i > 0:
            res.append(str1[i-1])
            i -= 1
        while j > 0:
            res.append(str2[j-1])
            j -= 1
        return ''.join(reversed(res))

class Solution {
public:
    string shortestCommonSupersequence(string str1, string str2) {
        int m = str1.size(), n = str2.size();
        vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (str1[i] == str2[j])
                    dp[i+1][j+1] = dp[i][j] + 1;
                else
                    dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
            }
        }
        string res = "";
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (str1[i-1] == str2[j-1]) {
                res += str1[i-1];
                --i; --j;
            } else if (dp[i-1][j] >= dp[i][j-1]) {
                res += str1[i-1];
                --i;
            } else {
                res += str2[j-1];
                --j;
            }
        }
        while (i > 0) {
            res += str1[i-1];
            --i;
        }
        while (j > 0) {
            res += str2[j-1];
            --j;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int m = str1.length(), n = str2.length();
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (str1.charAt(i) == str2.charAt(j))
                    dp[i+1][j+1] = dp[i][j] + 1;
                else
                    dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
            }
        }
        StringBuilder res = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (str1.charAt(i-1) == str2.charAt(j-1)) {
                res.append(str1.charAt(i-1));
                --i; --j;
            } else if (dp[i-1][j] >= dp[i][j-1]) {
                res.append(str1.charAt(i-1));
                --i;
            } else {
                res.append(str2.charAt(j-1));
                --j;
            }
        }
        while (i > 0) {
            res.append(str1.charAt(i-1));
            --i;
        }
        while (j > 0) {
            res.append(str2.charAt(j-1));
            --j;
        }
        return res.reverse().toString();
    }
}

var shortestCommonSupersequence = function(str1, str2) {
    let m = str1.length, n = str2.length;
    let dp = Array.from({length: m+1}, () => Array(n+1).fill(0));
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (str1[i] === str2[j])
                dp[i+1][j+1] = dp[i][j] + 1;
            else
                dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
        }
    }
    let res = [];
    let i = m, j = n;
    while (i > 0 && j > 0) {
        if (str1[i-1] === str2[j-1]) {
            res.push(str1[i-1]);
            i--; j--;
        } else if (dp[i-1][j] >= dp[i][j-1]) {
            res.push(str1[i-1]);
            i--;
        } else {
            res.push(str2[j-1]);
            j--;
        }
    }
    while (i > 0) {
        res.push(str1[i-1]);
        i--;
    }
    while (j > 0) {
        res.push(str2[j-1]);
        j--;
    }
    return res.reverse().join('');
};

Problem Description

Given two strings, str1 and str2, your task is to find the shortest string that has both str1 and str2 as subsequences. This string is called the Shortest Common Supersequence (SCS) of str1 and str2.

You must return one valid solution (there may be multiple correct answers).
Characters from str1 and str2 must appear in order, but may be interleaved in the supersequence.
Do not reuse characters; each character should only appear in the supersequence as many times as it appears in the original strings.

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

Thought Process

To solve this problem, we first need to understand what a supersequence is: a string that contains both str1 and str2 as subsequences. The shortest such string is the goal.

A brute-force approach would try all possible ways to merge the two strings, but this quickly becomes infeasible as the strings grow longer.

The key insight is that the overlap between str1 and str2 can be maximized by finding their Longest Common Subsequence (LCS). By aligning the LCS, we avoid repeating common characters and minimize the length of the supersequence.

Instead of generating all possible supersequences, we can:

Find the LCS of str1 and str2
Merge the two strings by “weaving” them together around their LCS

Solution Approach

The solution uses dynamic programming to find the LCS, then builds the shortest common supersequence by merging the two strings based on this LCS.

Compute the LCS DP Table:
- Create a 2D array dp where dp[i][j] is the length of the LCS of str1[0:i] and str2[0:j].
- Fill the table using:
  - If str1[i-1] == str2[j-1], then dp[i][j] = dp[i-1][j-1] + 1
  - Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Reconstruct the Shortest Common Supersequence:
- Start from the bottom-right of the DP table.
- While both indices are greater than 0:
  - If the characters match, add to the result and move diagonally up-left.
  - If not, move in the direction of the larger DP value, adding the corresponding character to the result.
- Add any remaining characters from either string.
- Reverse the result since we built it backwards.

This approach ensures that all characters from both strings are included in order, and common characters are not repeated unnecessarily.

Example Walkthrough

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

Step 1: Find LCS
The LCS of "abac" and "cab" is "ab".

Step 2: Build SCS
Trace both strings, merging them and only using common characters once:

Start with str1 = "abac", str2 = "cab"
First character of str2 is 'c', not in str1 at this point, so add 'c'.
Now align 'a' from both (since they’re common), add 'a' once.
Next, 'b' is also common, add 'b' once.
Leftover in str1 is 'a' and 'c', add them in order.

The result: "cabac"

Time and Space Complexity

Brute-force approach: Exponential time, as it tries all ways to merge (not feasible for large inputs).
Optimized DP approach:
- Time Complexity: O(m*n), where m and n are the lengths of str1 and str2. This is for filling the LCS DP table and reconstructing the answer.
- Space Complexity: O(m*n) for the DP table. Reconstruction uses O(m+n) for the result.

Summary

The shortest common supersequence problem can be efficiently solved by first finding the longest common subsequence (LCS) to maximize overlap, and then merging the two strings around this LCS. This dynamic programming approach ensures that all characters are included in order, avoids unnecessary repetition, and produces a minimal-length supersequence. The key insight is leveraging the LCS as a backbone for the merge, making the solution elegant and efficient.

AlgoMap.io

Want Help Cracking FAANG?