Shortest Common Super Sequence

LeetCode: Shortest Common Supersequence

Problem Statement

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple such strings exist, return any of them.

Intuition

We want to merge both strings while avoiding repetition of common characters.
Use LCS (Longest Common Subsequence) to find the overlapping parts and then build the SCS.

Length of SCS = str1.length() + str2.length() - LCS(str1, str2)

1. Recursion

Concept

We define f(i, j) as the shortest supersequence of str1[0..i] and str2[0..j].

Choice Diagram (IBH)

Java Code: Recursion

public class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        return scs(str1, str2, str1.length() - 1, str2.length() - 1);
    }

    private String scs(String s1, String s2, int i, int j) {
        if (i < 0) return s2.substring(0, j + 1);
        if (j < 0) return s1.substring(0, i + 1);

        if (s1.charAt(i) == s2.charAt(j)) {
            return scs(s1, s2, i - 1, j - 1) + s1.charAt(i);
        } else {
            String pick1 = scs(s1, s2, i - 1, j) + s1.charAt(i);
            String pick2 = scs(s1, s2, i, j - 1) + s2.charAt(j);
            return pick1.length() < pick2.length() ? pick1 : pick2;
        }
    }
}

Time Complexity: Exponential — O(2^(m+n))

2. Memoization (Top-Down DP)

Java Code: Memoization

public class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int n = str1.length(), m = str2.length();
        String[][] dp = new String[n][m];
        return scs(str1, str2, n - 1, m - 1, dp);
    }

    private String scs(String s1, String s2, int i, int j, String[][] dp) {
        if (i < 0) return s2.substring(0, j + 1);
        if (j < 0) return s1.substring(0, i + 1);

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

        if (s1.charAt(i) == s2.charAt(j)) {
            return dp[i][j] = scs(s1, s2, i - 1, j - 1, dp) + s1.charAt(i);
        } else {
            String pick1 = scs(s1, s2, i - 1, j, dp) + s1.charAt(i);
            String pick2 = scs(s1, s2, i, j - 1, dp) + s2.charAt(j);
            return dp[i][j] = pick1.length() < pick2.length() ? pick1 : pick2;
        }
    }
}

Time Complexity: O(m × n × (m+n)) (due to string building)

3. Tabulation (Bottom-Up DP) + Reconstruction

Java Code

public class Solution {
    public String shortestCommonSupersequence(String str1, String str2) {
        int n = str1.length(), m = str2.length();
        int[][] dp = new int[n + 1][m + 1];

        // Step 1: LCS Table
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (str1.charAt(i - 1) == str2.charAt(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]);
                }
            }
        }

        // Step 2: Reconstruct SCS from LCS table
        StringBuilder sb = new StringBuilder();
        int i = n, j = m;

        while (i > 0 && j > 0) {
            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                sb.append(str1.charAt(i - 1));
                i--; j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                sb.append(str1.charAt(i - 1));
                i--;
            } else {
                sb.append(str2.charAt(j - 1));
                j--;
            }
        }

        while (i > 0) sb.append(str1.charAt(--i));
        while (j > 0) sb.append(str2.charAt(--j));

        return sb.reverse().toString();
    }
}

Dry Run Example

str1 = "abac", str2 = "cab"

LCS = "ab"  
SCS = "cabac"

Time and Space Complexity

Approach Time Space
Recursion O(2^(n+m)) O(n+m)
Memoization O(n×m) O(n×m)
Tabulation O(n×m) O(n×m)

Summary