Shortest Common Supersequence

• Define a recursive function, say solve(s1, s2), that takes two strings and returns their shortest common supersequence.
• Base Case: If either string is empty, the SCS is simply the other non-empty string. Return it.
• Recursive Step:
  • If the first characters of s1 and s2 are the same (s1[0] == s2[0]): The common character can be used once. The result is this character prepended to the result of the recursive call on the rest of the strings: s1[0] + solve(s1.substring(1), s2.substring(1)).
  • If the first characters are different: We have two possibilities to form the supersequence.
    1. Include s1[0] in the supersequence and find the SCS of the rest of s1 and all of s2. Result: s1[0] + solve(s1.substring(1), s2).
    2. Include s2[0] in the supersequence and find the SCS of all of s1 and the rest of s2. Result: s2[0] + solve(s1, s2.substring(1)).
  • Compare the lengths of the two resulting strings from the above step and return the shorter one.

The core idea is to build the shortest common supersequence (SCS) character by character from the beginning. At each step, we compare the first characters of the current substrings of str1 and str2.

If the characters match, we know this character must be in the SCS. We add it to our result and proceed to find the SCS for the remaining parts of both strings.

If the characters do not match, we have a choice. We can either take the character from str1 and find the SCS for the rest of str1 and the entirety of str2, or we can take the character from str2 and find the SCS for str1 and the rest of str2. To ensure the final supersequence is the shortest, we recursively explore both paths and choose the one that yields a shorter result.

This method naturally leads to a recursive structure but creates an explosion of function calls for the same subproblems, making it impractical for the given constraints.

1// Note: This solution is for demonstration and will Time Limit Exceed.2class Solution {3    public String shortestCommonSupersequence(String str1, String str2) {4        // Base case: if one string is empty, the other is the SCS.5        if (str1.isEmpty()) {6            return str2;7        }8        if (str2.isEmpty()) {9            return str1;10        }11 12        // If first characters are the same, they contribute one char to SCS.13        if (str1.charAt(0) == str2.charAt(0)) {14            return str1.charAt(0) + shortestCommonSupersequence(str1.substring(1), str2.substring(1));15        } else {16            // If different, explore two paths and choose the shorter result.17            String res1 = str1.charAt(0) + shortestCommonSupersequence(str1.substring(1), str2);18            String res2 = str2.charAt(0) + shortestCommonSupersequence(str1, str2.substring(1));19            20            if (res1.length() < res2.length()) {21                return res1;22            } else {23                return res2;24            }25        }26    }27}

• Step 1: Compute the Longest Common Subsequence (LCS) DP Table.

  • Create a 2D array dp of size (m+1) x (n+1), where m = str1.length() and n = str2.length().
  • dp[i][j] will store the length of the LCS of str1.substring(0, i) and str2.substring(0, j).
  • Fill the table using the standard LCS recurrence relation:
    • If str1[i-1] == str2[j-1], then dp[i][j] = 1 + dp[i-1][j-1].
    • Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

• Step 2: Construct the SCS by Backtracking.

  • Initialize two pointers, i = m and j = n, and an empty StringBuilder for the result.
  • Traverse the dp table backwards from dp[m][n]:
    • If str1[i-1] == str2[j-1]: This character is common. Append it to the result, and move diagonally up-left (i--, j--).
    • If str1[i-1] != str2[j-1]: The characters are different. We must include both, but not at the same time. We check the dp table to see which character was excluded to form the LCS at the previous step.
      • If dp[i-1][j] > dp[i][j-1], it means the path to the LCS came from dp[i-1][j]. So, str1[i-1] is a non-common character that must be in the SCS. Append str1[i-1] and move up (i--).
      • Otherwise, the path came from dp[i][j-1]. Append the non-common character str2[j-1] and move left (j--).
  • After the loop, one of the pointers might still be greater than 0. Append the remaining part of the corresponding string.
  • Finally, reverse the constructed string to get the correct SCS.

The problem of finding the shortest common supersequence is closely related to finding the longest common subsequence. The length of the SCS is given by len(str1) + len(str2) - len(LCS(str1, str2)). While we can compute the LCS string first, a more direct method is to use the DP table generated during the LCS length calculation to build the SCS.

First, we populate a dp[m+1][n+1] table where dp[i][j] stores the length of the LCS between str1[0...i-1] and str2[0...j-1]. This takes O(m*n) time.

Next, we reconstruct the SCS. We start from the end of both strings (i=m, j=n) and build the SCS string backwards.

• If str1[i-1] and str2[j-1] are the same, this character is part of the LCS. We add it once to our result and move to consider the prefixes str1[0...i-2] and str2[0...j-2].
• If they are different, we must include both characters in the SCS eventually. We look at our dp table to decide which one to add now. The one that is not on the path to the longer LCS of the subproblems is added. For example, if dp[i-1][j] (LCS of str1 prefix and str2 full) is greater than dp[i][j-1], it means str1[i-1] is unique at this step and must be added. We then move to the subproblem that gave the longer LCS.

This process continues until we've processed both strings completely. The resulting string is built in reverse, so a final reversal is needed.

1class Solution {2    public String shortestCommonSupersequence(String str1, String str2) {3        int m = str1.length();4        int n = str2.length();5        6        // Step 1: Fill DP table for LCS lengths7        int[][] dp = new int[m + 1][n + 1];8        for (int i = 0; i <= m; i++) {9            for (int j = 0; j <= n; j++) {10                if (i == 0 || j == 0) {11                    dp[i][j] = 0;12                } else if (str1.charAt(i - 1) == str2.charAt(j - 1)) {13                    dp[i][j] = 1 + dp[i - 1][j - 1];14                } else {15                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);16                }17            }18        }19        20        // Step 2: Backtrack to build the SCS string21        StringBuilder scs = new StringBuilder();22        int i = m, j = n;23        while (i > 0 && j > 0) {24            if (str1.charAt(i - 1) == str2.charAt(j - 1)) {25                scs.append(str1.charAt(i - 1));26                i--;27                j--;28            } else if (dp[i - 1][j] > dp[i][j - 1]) {29                scs.append(str1.charAt(i - 1));30                i--;31            } else {32                scs.append(str2.charAt(j - 1));33                j--;34            }35        }36        37        // Append remaining characters from str1 or str238        while (i > 0) {39            scs.append(str1.charAt(i - 1));40            i--;41        }42        while (j > 0) {43            scs.append(str2.charAt(j - 1));44            j--;45        }46        47        return scs.reverse().toString();48    }49}