Shortest Common Supersequence | DP on Strings

The Shortest Common Supersequence (SCS) problem asks us to find the shortest possible string that contains both given strings ($S_1$ and $S_2$) as subsequences. This chapter builds directly upon the concepts of Longest Common Subsequence (LCS) and Printing LCS, demonstrating how foundational DP tables can be adapted to solve advanced string-transformation challenges.

1. Why Do We Need This? (Problem Statement & Status Quo)

When working with strings in data processing, diff tools, version control systems, and genomic sequencing, we often need to merge two sequences into a single unified sequence without altering the internal order of characters in either original string.

• Supersequence Definition: A string $Z$ is called a supersequence of $S_1$ and $S_2$ if both $S_1$ and $S_2$ are subsequences of $Z$.
• Naïve Approach: Simply concatenating $S_1$ and $S_2$ (e.g., brute + groot = brutegroot) yields a valid supersequence of length $10$, but it contains redundant characters.
• Goal: Find the Shortest Common Supersequence (SCS) and reconstruct the actual string.

2. Core Mental Model: The Overlapping Character Strategy

To make the resulting supersequence as short as possible, we must reuse the characters that both strings share in the correct relative order.

Real-Life Analogy

Mental Hook: Imagine two friends walking through a supermarket shopping list. Friend 1 needs brute and Friend 2 needs groot. Instead of buying items twice when both lists overlap on certain letters (like r and t), they walk together, purchase the shared items in a single stop, and only purchase unique items separately. The resulting path represents the shortest combined shopping trip.

If we have two strings:

• $S_1 =$ brute (Length $N = 5$)
• $S_2 =$ groot (Length $M = 5$)

Characters that appear in both strings in the correct relative order form the Longest Common Subsequence (LCS). For brute and groot, the LCS is rt (length $2$).

3. Calculating the Length of the Shortest Common Supersequence

To compute the length of the SCS mathematically:

1. Every character unique to $S_1$ must be included.
2. Every character unique to $S_2$ must be included.
3. The common characters (the LCS) should be included only once instead of twice.

Using our example:

The resulting shortest common supersequence is gbrootte or gbrnoutte (specifically, one valid optimal string is gbrdoutte or more accurately gbroute / gbroutoet — let's verify with the exact backtracking table: g b r o u o t e, length $8$).

4. Constructing the DP Table (LCS Foundation)

Before we can print the SCS string, we must build the standard 1-based indexing LCS DP table of size $(N+1) \times (M+1)$.

Recurrence Relations

• If characters match ($S_1[i-1] == S_2[j-1]$):

• If characters do not match:

5. Reconstructing the Shortest Common Supersequence (Backtracking)

Starting from the bottom-right corner of the DP table (i = N, j = M), we trace our path back to (0, 0) using the following rules:

1. If characters match ($S_1[i-1] == S_2[j-1]$):
   • Add the character to our answer string once.
   • Move diagonally: i--, j--.
2. If characters do not match (and dp[i-1][j] > dp[i][j-1]):
   • We moved up from the previous row. This means $S_1[i-1]$ was not part of the LCS and was bypassed.
   • Add $S_1[i-1]$ to our answer.
   • Move up: i--.
3. Otherwise (moving left):
   • We moved left from the previous column. This means $S_2[j-1]$ was bypassed.
   • Add $S_2[j-1]$ to our answer.
   • Move left: j--.
4. Exhaustion Phase:
   • Once either i or j hits 0, collect all remaining characters from the non-exhausted string.
5. Reverse the Result:
   • Because we backtrack from end to start, reverse the final constructed string to get the correct order.

6. Complete C++ Implementation

Here is the complete, production-grade implementation for finding and printing the Shortest Common Supersequence:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string shortestCommonSupersequence(string str1, string str2) {
    int n = str1.length();
    int m = str2.length();
    
    // Step 1: Create and populate the LCS DP table
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    // Step 2: Backtrack from DP table to construct SCS
    int i = n, j = m;
    string ans = "";
    
    while (i > 0 && j > 0) {
        if (str1[i - 1] == str2[j - 1]) {
            ans += str1[i - 1]; // Common character included once
            i--;
            j--;
        } 
        else if (dp[i - 1][j] > dp[i][j - 1]) {
            ans += str1[i - 1]; // Character from str1 was bypassed
            i--;
        } 
        else {
            ans += str2[j - 1]; // Character from str2 was bypassed
            j--;
        }
    }
    
    // Step 3: Add remaining characters from str1 if any
    while (i > 0) {
        ans += str1[i - 1];
        i--;
    }
    
    // Step 4: Add remaining characters from str2 if any
    while (j > 0) {
        ans += str2[j - 1];
        j--;
    }
    
    // Step 5: Reverse since we backtracked from end to start
    reverse(ans.begin(), ans.end());
    
    return ans;
}

int main() {
    string s1 = "brute";
    string s2 = "groot";
    cout << "Shortest Common Supersequence: " << shortestCommonSupersequence(s1, s2) << endl;
    return 0;
}

7. Complexity Analysis

Summary and Key Takeaways

• Core Definition: The Shortest Common Supersequence (SCS) combines two strings into the shortest possible string containing both as subsequences.
• Length Formula: $\text{Length} = N + M - \text{Length of LCS}$.
• LCS Dependency: Solving DP on strings problems heavily relies on a solid understanding of the Longest Common Subsequence (LCS) table and its recurrence relations.
• Character Merging: Matching characters between strings are included exactly once in the final supersequence to minimize total length.
• Backtracking Mechanics: When characters do not match, we follow the larger value in the DP table (dp[i-1][j] vs dp[i][j-1]) to determine which non-matching character to append.
• Cleanup Phase: Always remember to flush remaining characters from whichever string (str1 or str2) has not yet reached index $0$.
• String Reversal: Because backtracking starts from the bottom-right corner, the accumulated result must be reversed at the end.