1092: Shortest-Common-Supersequence-
Hard

Alas, I have uploaded the write-up for this question.

After misreading this question a billion times, I realised you can break this question down into several portions. It asks you to find the shortest string that has both str1 and str2 as subsequences. To accomplish this, it is much easier to instead:

To find the largest common subsequence, we can just use dynamic programming to first find the length of the largest common subsequence.

First, we can initialise the 2D matrix dp with dimensions str1.size() + 1 and str2.size() + 2 (we make it +1 height and width so the DP algorithm does not go out of bounds), where dp[i1][i2] contains the length of the largest common subsequence for str1[0:i1] and str2[0:i2]. Then, when we iterate through str1 and str2, we check for:

Then, we know dp[str1.size()][str2.size()] contains the length of the largest common subsequence.

We can then use backtracking to find out what the letters present in the largest common subsequence is. Note, we do not directly deal with storing strings inside the dp matrix, as that would exacerbate the time taken for each operation in the O(n^2) DP algorithm, and would definitely exceed the memory limit for longer strings.

To do this, we can simply use a recursive function that adds a letter whenever str1[i1] == str2[i2] and dp[i1+1][i2+1] == dp[i1][i2] + 1 as satisfying both these equalities signifies that we added the letter str1[i1] to the previous largest common subsequence to form the current largest common subsequence, subseq.

Finally, letting ans be the string we return, we can do an iteration through subseq, adding letters from str1 and str2 only when they do not equal subseq[i], 0 <= i < subseq.size(). Then, after the iteration, we can add the remaining letters from str1 and str2 to ans, to get an example of the shortest string that has both str1 and str2 as subsequences.

code

class Solution {
public:
    string shortestCommonSubsequence(int i1, int i2, string &str1, string &str2, vector<vector<int>> &dp) {
        if (i1 < 0 || i2 < 0) return "";
        if (str1[i1] == str2[i2] && dp[i1+1][i2+1] == dp[i1][i2] + 1) {
            string res = shortestCommonSubsequence(i1-1, i2-1, str1, str2, dp);
            res += str1[i1];
            return res;
        } else if (dp[i1+1][i2] < dp[i1][i2+1]) {
            return shortestCommonSubsequence(i1-1, i2, str1, str2, dp);
        } else {
            return shortestCommonSubsequence(i1, i2-1, str1, str2, dp);
        }
    }
    string shortestCommonSupersequence(string str1, string str2) {
        vector<vector<int>> dp (str1.size()+1, vector<int>(str2.size()+1));

        for (int i = 0; i < str1.size(); ++i) {
            for (int j = 0; j < str2.size(); ++j) {
                dp[i+1][j+1] = (str1[i] == str2[j]) ? dp[i][j] + 1 : max(dp[i+1][j], dp[i][j+1]);
            }
        }

        string subseq = shortestCommonSubsequence(str1.size()-1, str2.size()-1, str1, str2, dp);
        int i1 = 0;
        int i2 = 0;
        string ans = "";
        for (int index = 0; index < subseq.size(); ++index) {
            while (str1[i1] != subseq[index]) {
                ans += str1[i1++];
            }
            while (str2[i2] != subseq[index]) {
                ans += str2[i2++];
            }
            ans += subseq[index];
            ++i1;
            ++i2;
        }
        while (i1 < str1.size()) {
            ans += str1[i1++];
        }
        while (i2 < str2.size()) {
            ans += str2[i2++];
        }
        return ans;
    }
};

complexity