Shortest Common Supersequence

Share a letter when both strings agree, pay one character when they don't

time O(m * n)space O(m * n)

A supersequence must carry every letter of both strings, in order, but a letter both strings agree on at this position can be written ONCE and still count for both. Compare the last letters of the two prefixes: if they match, share that letter and fall back to the diagonal cell. If they differ, the supersequence has to spend a character on one of them alone, so take whichever neighbour (up or left) is cheaper and add one. The arrows in the table are exactly that choice, made visible.

Details

Animated on: str1 = "abac", str2 = "cab" — find the length of the shortest string that contains both as subsequences.

Problem:Shortest Common SupersequenceHard

Share a letter when both strings agree, pay one character when they don't

step 1 / 16

rows = prefixes of "abac", columns = prefixes of "cab"

-cab

-abac

dp[i][j] is the shortest string containing both the first i letters of "abac" and the first j of "cab" as subsequences. Two empty prefixes need nothing, so dp[0][0] = 0.

Pseudocode

1FUNCTION shortestCommonSupersequence(str1, str2)
2  m <- LENGTH(str1)
3  n <- LENGTH(str2)
4  FOR i FROM 0 TO m
5    dp[i][0] <- i
6  FOR j FROM 0 TO n
7    dp[0][j] <- j
8  FOR i FROM 1 TO m
9    FOR j FROM 1 TO n
10      IF str1[i-1] = str2[j-1]
11        dp[i][j] <- 1 + dp[i-1][j-1]
12      ELSE
13        dp[i][j] <- 1 + MIN(dp[i-1][j], dp[i][j-1])
14  RETURN dp[m][n]

← / → step · space play · Home restart

Every step in words

Show all 16 steps

dp[i][j] is the shortest string containing both the first i letters of "abac" and the first j of "cab" as subsequences. Two empty prefixes need nothing, so dp[0][0] = 0.
Against an empty str2 the supersequence must still carry all of "abac" verbatim, so dp[4][0] = 4.
Same argument mirrored: dp[0][3] = 3. Every other cell now has both neighbours it needs already on the board.
'a' does not match 'c', so the supersequence must add one of them on its own: up gives 1, left gives 1. Cheapest is 1, so dp[1][1] = 2 by choosing to carry 'a' from str1.
'a' and 'a' are the same letter, so one shared copy covers both strings here: dp[1][2] = 1 + dp[0][1] = 2.
'a' does not match 'b', so the supersequence must add one of them on its own: up gives 3, left gives 2. Cheapest is 2, so dp[1][3] = 3 by choosing to carry 'b' from str2.
'b' does not match 'c', so the supersequence must add one of them on its own: up gives 2, left gives 2. Cheapest is 2, so dp[2][1] = 3 by choosing to carry 'b' from str1.
'b' does not match 'a', so the supersequence must add one of them on its own: up gives 2, left gives 3. Cheapest is 2, so dp[2][2] = 3 by choosing to carry 'b' from str1.
'b' and 'b' are the same letter, so one shared copy covers both strings here: dp[2][3] = 1 + dp[1][2] = 3.
'a' does not match 'c', so the supersequence must add one of them on its own: up gives 3, left gives 3. Cheapest is 3, so dp[3][1] = 4 by choosing to carry 'a' from str1.
'a' and 'a' are the same letter, so one shared copy covers both strings here: dp[3][2] = 1 + dp[2][1] = 4.
'a' does not match 'b', so the supersequence must add one of them on its own: up gives 3, left gives 4. Cheapest is 3, so dp[3][3] = 4 by choosing to carry 'a' from str1.
'c' and 'c' are the same letter, so one shared copy covers both strings here: dp[4][1] = 1 + dp[3][0] = 4.
'c' does not match 'a', so the supersequence must add one of them on its own: up gives 4, left gives 4. Cheapest is 4, so dp[4][2] = 5 by choosing to carry 'c' from str1.
'c' does not match 'b', so the supersequence must add one of them on its own: up gives 4, left gives 5. Cheapest is 4, so dp[4][3] = 5 by choosing to carry 'c' from str1.
dp[4][3] = 5: the shortest string containing both "abac" and "cab" as subsequences has 5 characters.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Shortest Common Supersequence in the editor All Dynamic Programming problems Back to roadmap