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 <= 500s1 and s2 consist of lowercase English letters
Hints for Shortest Common Supersequence Length
Hint 1
Writing
s1followed bys2always works and has lengthn + m. How much can be saved?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.
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
- Compute the LCS length with the standard table:
lcs[i][j] = lcs[i-1][j-1] + 1whens1[i-1] == s2[j-1], elsemax(lcs[i-1][j], lcs[i][j-1]). - 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
iandj, not0.
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