Problem Statement

Given two string str1 and str2, return the length of their shortest common super-sequence (SCS).

A common super-sequence of two string is a string that contains both str1 and str2` as subsequences.

The goal is not to construct the SCS, but just to compute its length.

Examples

Example 1:

Input: str1 = "abac", str2 = "can"
Output: 5

Explanation: LCS = "ab"
             SCS = "cabac"
             
             str1 + str2 = 7
             Complete Length - LCS = 7 - 2 = 5

Example 2:

Input: str1 = "geek", str2 = "eke"
Output: 5

Explanation: LCS = "ek"
             SCS = "geeke"
             
             str1 + str2 = 4 + 3 = 7
             Complete Length - LCS = 7 - 2 = 5

Different Approaches

1️⃣ Recursive (Brute Force) Approach

Intuition:

• Try all ways of building supersequences by either:
  • Matching characters → include one and recurse
  • Not matching → include both possibilities and take minimum

Code:

int scsLength(string str1, string str2, int i, int j) {
    if (i == 0) return j;
    if (j == 0) return i;

    if (str1[i - 1] == str2[j - 1])
        return 1 + scsLength(str1, str2, i - 1, j - 1);
    else
        return 1 + min(scsLength(str1, str2, i - 1, j), scsLength(str1, str2, i, j - 1));
}

Complexity Analysis:

• Time Complexity:O(2^(n+m))
  • Exponential
• Space Complexity:O(n+m)
  • Due to recursion stack

2️⃣ Memoization

Intuition:

Store already computed results using recursion + memoization.

Code:

int dp[1001][1001];

int solve(string& str1, string& str2, int i, int j) {
    if (i == 0) return j;
    if (j == 0) return i;

    if (dp[i][j] != -1) return dp[i][j];

    if (str1[i - 1] == str2[j - 1])
        return dp[i][j] = 1 + solve(str1, str2, i - 1, j - 1);
    else
        return dp[i][j] = 1 + min(solve(str1, str2, i - 1, j), solve(str1, str2, i, j - 1));
}

int shortestCommonSupersequence(string str1, string str2) {
    memset(dp, -1, sizeof(dp));
    return solve(str1, str2, str1.length(), str2.length());
}

Complexity Analysis:

• Time Complexity:O(n*m)
• Space Complexity:O(n*m)
  • For dp plus O(n+m) for the recursion stack

3️⃣ Tabulation

Intuition:

Fill a 2D DP table where dp[i][j] = SCS length for str1[0…i-1] and str2[0…j-1].

Code:

int shortestCommonSupersequence(string str1, string str2) {
    int n = str1.length(), m = str2.length();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

    for (int i = 0; i <= n; ++i)
        dp[i][0] = i;
    for (int j = 0; j <= m; ++j)
        dp[0][j] = j;

    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] = 1 + min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    return dp[n][m];
}

Complexity Analysis:

• Time Complexity:O(n*m)
• Space Complexity:O(n*m)
  • No recursion stack

4️⃣ Using LCS Directly (Most Efficient)

Intuition:

1. First compute the length of LCS

2. Then use formula:

   SCS length = str1.length() + str2.length() - LCS length

Code:

int lcs(string& str1, string& str2) {
    int n = str1.length(), m = str2.length();
    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]);
        }
    }

    return dp[n][m];
}

int shortestCommonSupersequence(string str1, string str2) {
    int lcsLength = lcs(str1, str2);
    return str1.length() + str2.length() - lcsLength;
}

Complexity Analysis:

• Time Complexity:O(n*m)
• Space Complexity:O(n*m)