The shortest common supersequence
Given strings a and b, return the length of the shortest string that has both a
and b as subsequences.
Examples
| Input | Output | Why |
|---|---|---|
a = "abac", b = "cab" | 5 | "cabac". |
a = "abc", b = "def" | 6 | Nothing can be shared. |
a = "geek", b = "eke" | 5 | "geeke". |
Constraints
- 0 ≤ a.length, b.length ≤ 1000
- Lowercase English letters
Hints
Hint 1
A supersequence writes every character of both strings, but a character common to both, in a shared order, needs writing only once.
Hint 2
The most that can be shared is the longest common subsequence.
Hint 3
Directly: scs[i][j] = 1 + scs[i − 1][j − 1] on a match, else 1 + min(scs[i − 1][j], scs[i][j − 1]).
Where people lose marks
- Returning |a| + |b|, which ignores sharing.
- Base cases of 0 instead of the remaining length of the other string.
Dry run on "abac","cab"
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 2∅00010203a00011213b00011223a00011223c00111223
The LCS table for "abac" and "cab": the longest common subsequence has length 2.
-
Step 2 / 2
Shared characters are written once: 4 + 3 − 2 = 5.
How to think about it
Merge the two strings, writing a character once when it serves both. The characters written once form a common
subsequence, so the length is |a| + |b| − (number shared), minimised by sharing the longest common
subsequence. The direct two-sequence recurrence says the same: on a match, write the character once and move both;
otherwise write one string's last character and move that string only, choosing the cheaper. Base cases: with one string
empty, the answer is the other's length.
Complexity. Time O(|a| · |b|) · Space O(|b|)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def scs_length(a, b):
m = len(b)
prev = list(range(m + 1)) # a empty: write all of b[:j]
for i in range(1, len(a) + 1):
cur = [i] + [0] * m # b empty: write all of a[:i]
for j in range(1, m + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1] + 1 # write the shared character once
else:
cur[j] = 1 + min(prev[j], cur[j - 1])
prev = cur
return prev[m]#include <algorithm>
#include <string>
#include <vector>
int solve(std::string a, std::string b) {
const int m = b.size();
std::vector<int> prev(m + 1), cur(m + 1);
for (int j = 0; j <= m; ++j) prev[j] = j;
for (int i = 1; i <= (int)a.size(); ++i) {
cur[0] = i;
for (int j = 1; j <= m; ++j)
cur[j] = a[i - 1] == b[j - 1] ? prev[j - 1] + 1 : 1 + std::min(prev[j], cur[j - 1]);
std::swap(prev, cur);
}
return prev[m];
}class Solution {
public int scsLength(String a, String b) {
int m = b.length();
int[] prev = new int[m + 1], cur = new int[m + 1];
for (int j = 0; j <= m; j++) prev[j] = j;
for (int i = 1; i <= a.length(); i++) {
cur[0] = i;
for (int j = 1; j <= m; j++)
cur[j] = a.charAt(i - 1) == b.charAt(j - 1) ? prev[j - 1] + 1 : 1 + Math.min(prev[j], cur[j - 1]);
int[] t = prev; prev = cur; cur = t;
}
return prev[m];
}
}function scsLength(a, b) {
const m = b.length;
let prev = Array.from({ length: m + 1 }, (_, j) => j);
for (let i = 1; i <= a.length; i++) {
const cur = [i, ...new Array(m).fill(0)];
for (let j = 1; j <= m; j++)
cur[j] = a[i - 1] === b[j - 1] ? prev[j - 1] + 1 : 1 + Math.min(prev[j], cur[j - 1]); // shared once
prev = cur;
}
return prev[m];
}fn solve(a: &str, b: &str) -> i64 {
let b: Vec<char> = b.chars().collect();
let m = b.len();
let mut prev: Vec<i64> = (0..=m as i64).collect();
for (i, ch) in a.chars().enumerate() {
let mut cur = vec![0i64; m + 1];
cur[0] = i as i64 + 1;
for j in 1..=m {
cur[j] = if ch == b[j - 1] { prev[j - 1] + 1 } else { 1 + prev[j].min(cur[j - 1]) };
}
prev = cur;
}
prev[m]
}solve :: String -> String -> Int
solve a b = last (foldl step [0 .. length b] (zip [1 ..] a))
where
-- the row for a[:i] from the row for a[:i - 1]
step prev (i, ch) = scanl cell i (zip3 b prev (tail prev))
where cell left (c, diag, up) = if c == ch then diag + 1 else 1 + min up leftVariants to try
- Return the supersequence itself (LeetCode 1092): walk back through the table.
- Count the shortest supersequences.
- Three strings.
Next problems
How many times one string appears in another
Count the ways to delete characters from s so that what remains is t. Use s's last character for t's last character, or do not.
Open the problem → Medium25 minIs a string an interleaving of two others?
Decide whether s3 can be built by merging s1 and s2, each kept in order. The state is how much of each has been used.
Open the problem → Hard30 minWildcard pattern matching
In the pattern, ? matches one character and * matches any run, including none. Does the pattern match the whole string?
Open the problem →Write a solution and run it against the real test table.
Keep going
How many times one string appears in another
Count the ways to delete characters from s so that what remains is t. Use s's last character for t's last character, or do not.
Open the problem → Medium25 minIs a string an interleaving of two others?
Decide whether s3 can be built by merging s1 and s2, each kept in order. The state is how much of each has been used.
Open the problem → Hard30 minWildcard pattern matching
In the pattern, ? matches one character and * matches any run, including none. Does the pattern match the whole string?
Open the problem → Dynamic programmingThe pattern behind it
Write the recursion, notice the repeats, fill a table in an order that makes each entry final.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.