Dynamic Programming • Traceback

Shortest Common Supersequence

Find the shortest string that has both given strings as subsequences. It's intimately tied to finding the Longest Common Subsequence (LCS).

Try Interactive Simulator

Overview

A supersequence contains both strings. To make it the *shortest* possible, we must reuse as many characters as possible. What characters can be reused? The characters in their LCS!

The Math

The length of the SCS is exactly: `Length(S1) + Length(S2) - Length(LCS)`. We subtract the LCS because those characters are shared and only need to be written once.

Printing the SCS

We trace back through the LCS DP table. If characters match, we add it to our result ONCE. If they don't match, we add the character from the string we are "dropping" and move towards the larger DP value.

Flushing Leftovers

If we hit the edge of the DP table (`i=0` or `j=0`), we just append whatever is left of the other string, because we must include all characters to form a valid supersequence.

S1 \ S2	c	a	b
""	0	0	0
a	0	1	1
b	0	1	2
a	0	2	2
c	1	2	2

Code Tracker

:::

1let result = '';

2let i = s1.length, j = s2.length;

3while (i > 0 && j > 0) {

4 if (s1[i - 1] === s2[j - 1]) {

5 result = s1[i - 1] + result; // Add once

6 i--; j--;

7 } else if (dp[i - 1][j] > dp[i][j - 1]) {

8 result = s1[i - 1] + result; // Add s1 char

9 i--;

10 } else {

11 result = s2[j - 1] + result; // Add s2 char

12 j--;

13 }

14}

15// Add remaining chars

16while (i > 0) { result = s1[i - 1] + result; i--; }

17while (j > 0) { result = s2[j - 1] + result; j--; }

18return result;