Shortest Common Supersequence Length

Medium
1610.

Shortest Common Supersequence Length

Shortest Common Supersequence Length is a medium coding problem on strings and dynamic programming, asked in Amazon and Microsoft interviews.

Given two strings s1 and s2, return the length of the shortest string that has both s1 and s2 as subsequences (a common supersequence).

A subsequence keeps characters in their original order but may skip any of them, so a supersequence of both strings must contain all of s1's characters in order and all of s2's characters in order, sharing characters where it can.

Example 1

Input
s1 = "abcd", s2 = "xycd"
Output
6
Explanation
"abxycd" (or "xyabcd") contains both; "cd" is shared.

Example 2

Input
s1 = "efgh", s2 = "jghi"
Output
6
Explanation
"ejfghi" works: "gh" is shared.

Example 3

Input
s1 = "geek", s2 = "eke"
Output
5
Explanation
"geeke" contains "geek" and "eke".

Constraints

  • 1 <= s1.length, s2.length <= 500
  • s1 and s2 consist of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var shortestCommonSupersequence = function(s1, s2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Shortest Common Supersequence Length — Problem & Solution

Shortest Common Supersequence Length solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Shortest Common Supersequence Length is a medium coding problem on strings and dynamic programming, asked in Amazon and Microsoft interviews.

  • Difficulty: Medium
  • Topics: Strings, Dynamic Programming
  • Asked at: Amazon, Microsoft
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given two strings s1 and s2, return the length of the shortest string that has both s1 and s2 as subsequences (a common supersequence).

A subsequence keeps characters in their original order but may skip any of them, so a supersequence of both strings must contain all of s1's characters in order and all of s2's characters in order, sharing characters where it can.

Example 1

Input: s1 = "abcd", s2 = "xycd"
Output: 6
Explanation: "abxycd" (or "xyabcd") contains both; "cd" is shared.

Example 2

Input: s1 = "efgh", s2 = "jghi"
Output: 6
Explanation: "ejfghi" works: "gh" is shared.

Example 3

Input: s1 = "geek", s2 = "eke"
Output: 5
Explanation: "geeke" contains "geek" and "eke".

Constraints

  • 1 <= s1.length, s2.length <= 500
  • s1 and s2 consist of lowercase English letters

Hints for Shortest Common Supersequence Length

  1. Hint 1

    Writing s1 followed by s2 always works and has length n + m. How much can be saved?

  2. Hint 2

    A character can be written once for both strings only if it is part of a sequence the two strings have in common, in order.

  3. Hint 3

    The saving is exactly the length of the longest common subsequence: the answer is n + m - LCS(s1, s2).

How to solve Shortest Common Supersequence Length

In a common supersequence, every position is used by s1, by s2, or by both. The positions used by both spell out a common subsequence of the two strings, so at most LCS characters can be shared — and an LCS can always be shared, by merging the two strings around it.

Approach

  1. Compute the LCS length with the standard table: lcs[i][j] = lcs[i-1][j-1] + 1 when s1[i-1] == s2[j-1], else max(lcs[i-1][j], lcs[i][j-1]).
  2. Return n + m - lcs[n][m].

Why it works

Lower bound: the shared positions of any common supersequence form a common subsequence, so its length is at least n + m - LCS. Upper bound: walk both strings along an LCS, emitting the characters of each string between consecutive LCS characters and each LCS character once — that string has length exactly n + m - LCS and contains both inputs.

Complexity

  • Time — O(n * m)
  • Space — O(m) with two rows

Pitfalls

  • Using the longest common substring instead of subsequence undercounts the sharing.
  • Only the length is asked; building the actual string needs the full table to backtrack.
  • Empty-prefix rows of the direct supersequence table are i and j, not 0.

Reference solution

Python

def shortestCommonSupersequence(s1: str, s2: str) -> int:
    n, m = len(s1), len(s2)
    prev = [0] * (m + 1)
    for i in range(1, n + 1):
        cur = [0] * (m + 1)
        ci = s1[i - 1]
        for j in range(1, m + 1):
            if ci == s2[j - 1]:
                cur[j] = prev[j - 1] + 1
            else:
                cur[j] = prev[j] if prev[j] > cur[j - 1] else cur[j - 1]
        prev = cur
    return n + m - prev[m]

Java

public static int shortestCommonSupersequence(String s1, String s2) {
    int n = s1.length(), m = s2.length();
    int[] prev = new int[m + 1], cur = new int[m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) cur[j] = prev[j - 1] + 1;
            else cur[j] = Math.max(prev[j], cur[j - 1]);
        }
        int[] t = prev; prev = cur; cur = t;
    }
    return n + m - prev[m];
}

C++

int shortestCommonSupersequence(string s1, string s2) {
    int n = s1.size(), m = s2.size();
    vector<int> prev(m + 1, 0), cur(m + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i - 1] == s2[j - 1]) cur[j] = prev[j - 1] + 1;
            else cur[j] = max(prev[j], cur[j - 1]);
        }
        swap(prev, cur);
    }
    return n + m - prev[m];
}

JavaScript

var shortestCommonSupersequence = function(s1, s2) {
    var n = s1.length, m = s2.length;
    var prev = new Array(m + 1).fill(0);
    var cur = new Array(m + 1).fill(0);
    for (var i = 1; i <= n; i++) {
        for (var j = 1; j <= m; j++) {
            if (s1.charCodeAt(i - 1) === s2.charCodeAt(j - 1)) cur[j] = prev[j - 1] + 1;
            else cur[j] = Math.max(prev[j], cur[j - 1]);
        }
        var t = prev; prev = cur; cur = t;
    }
    return n + m - prev[m];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Dynamic Programming