Shortest Common Supersequence

hard dynamic programming lcs string

Problem

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid answers, return any of them. A string s is a subsequence of t if deleting some (possibly zero) characters of t yields s.

Inputstr1 = "abac", str2 = "cab"

Output"cabac"

"cabac" contains "abac" (delete the leading c) and "cab" (delete the trailing ac). The shared subsequence "ab" is written only once.

str1

str2

def shortest_common_supersequence(str1, str2):
    m, n = len(str1), len(str2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    i, j, res = 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
    res.append(str1[:i]); res.append(str2[:j])
    return "".join(reversed(res))

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

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 = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = str1.charAt(i - 1) == str2.charAt(j - 1)
                    ? dp[i - 1][j - 1] + 1
                    : Math.max(dp[i - 1][j], dp[i][j - 1]);
        StringBuilder sb = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) { sb.append(str1.charAt(--i)); j--; }
            else if (dp[i - 1][j] >= dp[i][j - 1]) sb.append(str1.charAt(--i));
            else sb.append(str2.charAt(--j));
        }
        sb.append(new StringBuilder(str1.substring(0, i)).reverse());
        sb.append(new StringBuilder(str2.substring(0, j)).reverse());
        return sb.reverse().toString();
    }
}

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 = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            dp[i][j] = str1[i - 1] == str2[j - 1]
                ? dp[i - 1][j - 1] + 1
                : max(dp[i - 1][j], dp[i][j - 1]);
    int i = m, j = n;
    string res;
    while (i > 0 && j > 0) {
        if (str1[i - 1] == str2[j - 1]) { res += str1[--i]; j--; }
        else if (dp[i - 1][j] >= dp[i][j - 1]) res += str1[--i];
        else res += str2[--j];
    }
    res += string(str1.rend() - i, str1.rend());
    res += string(str2.rend() - j, str2.rend());
    reverse(res.begin(), res.end());
    return res;
}

Explanation

We want the shortest string that contains both str1 and str2 as subsequences. The key insight is that the parts they share should be written only once, and that shared part is exactly their longest common subsequence (LCS).

So the solution has two phases. First it builds the classic LCS table dp, where dp[i][j] is the LCS length of the first i letters of str1 and first j of str2. When the current letters match, it extends the diagonal (dp[i-1][j-1] + 1); otherwise it takes the better of dropping a letter from either side.

The second phase walks backward from dp[m][n] to the origin to actually build the answer. On a match, that letter belongs to both strings, so emit it once and step diagonally. On a mismatch, emit the letter from whichever direction the LCS came from and step that way. Any leftover prefix of either string is prepended at the end.

Example: str1 = "abac", str2 = "cab". Their LCS is "ab", written once. Weaving in the extra letters around it produces "cabac" — which contains both inputs and is as short as possible.

Since the result is collected in reverse during the walk, the code reverses it before returning. The table costs O(m·n) time and space.

Time: O(m·n) Space: O(m·n)