Shortest Common Supersequence

Print combination of both the string by making them smallest

Shortest Common Supersequence

Problem Statement

Given two strings, str1 and str2, find the shortest common supersequence.

The shortest common supersequence is the shortest string that contains both str1 and str2 as subsequences.

Note: The problem may have multiple valid answers. Any string that is a valid shortest common supersequence will be accepted.

Examples

Example 1

• Input: str1 = "mno", str2 = "nop"
• Output: "mnop"
• Explanation: The shortest common supersequence is "mnop". It contains "mno" as the first three characters and "nop" as the last three characters.

Example 2

• Input: str1 = "dynamic", str2 = "program"
• Output: "dynprogramic"
• Explanation: It includes all characters from both "dynamic" and "program", with minimal overlap. For example, "dynamic" appears as "dyn...amic" and "program" appears as "...program...".

Understanding the Goal

A Supersequence is a string that contains both str1 and str2 as subsequences. To make it the shortest possible, we must find the characters they share (the Longest Common Subsequence) and write those shared characters only once, filling in the rest of the non-matching characters around them.

Before we can build the Shortest Common Supersequence (SCS), we need to understand how to trace a path through a Dynamic Programming (DP) table to print the Longest Common Subsequence (LCS).

Prerequisite: Printing the Longest Common Subsequence (LCS)

When we build a DP table for the LCS, the value at dp[i][j] tells us the length of the common subsequence up to index i of string 1 and index j of string 2.

To actually print the string, we start at the bottom-right of the table and trace our way backwards to the top-left.

The DP Table Visualized

Let's use Example 1 (str1 = "mno" and str2 = "nop") to build our DP table. The Longest Common Subsequence here is "no".

How to trace backward:

1. Start at the bottom-right (dp[3][3], which holds the value 2).
2. If characters match: Add the character to your answer, and move diagonally up-left (i - 1, j - 1).
3. If characters DO NOT match: Look at the cell directly above (dp[i-1][j]) and the cell directly to the left (dp[i][j-1]). Move in the direction of the larger number.

function printLCS(s1, s2) {
    let n = s1.length;
    let m = s2.length;

    // Create DP table initialized with 0
    let dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));

    // Fill DP table
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (s1[i - 1] === s2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // Backtrack to find LCS string
    let len = dp[n][m];
    let lcs = new Array(len);
    let index = len - 1;
    let i = n, j = m;

    while (i > 0 && j > 0) {
        if (s1[i - 1] === s2[j - 1]) {
            // Characters match: Add to result and move diagonally
            lcs[index] = s1[i - 1];
            index--;
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            // Move Up
            i--;
        } else {
            // Move Left
            j--;
        }
    }

    return lcs.join('');
}

Modifying for the Shortest Common Supersequence

To build the Shortest Common Supersequence, we use the exact same DP table and the exact same backward tracing logic, but we change what we record.

• In the LCS, we only saved a character when there was a match.
• In the SCS, we must save all characters from both strings.
• The Trick: When characters match, we write that character down only once and move diagonally. When they don't match, we write down whichever character we are leaving behind as we move UP or LEFT.

Because we are building this string backwards, we must reverse the final result before returning it.

The Algorithm

1. Build the LCS DP table exactly as before.
2. Start backtracking from dp[n][m].
3. If s1[i-1] === s2[j-1]: Add the character once, and decrement both i and j (move diagonally).
4. If they don't match and we move UP (dp[i-1][j] > dp[i][j-1]): Add s1[i-1] to the result and decrement i.
5. If they don't match and we move LEFT: Add s2[j-1] to the result and decrement j.
6. Once one of the strings is exhausted (either i or j hits 0), add the remaining characters of the other string.
7. Reverse the final string.

function shortestCommonSupersequence(s1, s2) {
    let n = s1.length;
    let m = s2.length;
    
    // Create DP table initialized with 0
    let dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));

    // Fill DP table
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= m; j++) {
            if (s1[i - 1] === s2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    let res = "";
    let i = n, j = m;
    
    // Backtrack to build the supersequence
    while (i > 0 && j > 0) {
        if (s1[i - 1] === s2[j - 1]) {
            // Match: Add once, move diagonally
            res += s1[i - 1];
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            // Mismatch (Moving Up): Add s1's character
            res += s1[i - 1];
            i--;
        } else {
            // Mismatch (Moving Left): Add s2's character
            res += s2[j - 1];
            j--;
        }
    }
    
    // Add any remaining characters from s1
    while (i > 0) {
        res += s1[--i];
    }
        
    // Add any remaining characters from s2
    while (j > 0) {
        res += s2[--j];
    }

    // Since we built the string backwards, reverse it
    return res.split('').reverse().join('');
}