Dynamic Programming: Length of Shortest Common Supersequence

Problem Statement:

You are given 2 strings, you need to return the length of shortest common supersequence.

A super sequence is a string that has both string 1 and string 2.

Example

Input:
str1 = “abac”
str2 = “cab”

Output: 5

Why?

“cabac” is the shortest common supersequence where both the strings are present.

Solution

First let us understand the worst case scenario:

To get the super sequence, you need to add both the strings “str1 + str2”
So the o/p at worst case will be: abac + cab = abaccab of length 7.
But if you observe carefully, you can wee that there are multiple characters repeating, like “ab”.

So from that we can observe that “ab” is the longest common subsequence on the above 2 strings.

So to get the result, we need to find the LCS of the 2 strings and then subtract from the total length of the string to arrive at the solution.

We have followed bottom up approach to get the LCS of the 2 strings.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;

int lcs_bottom_up(string text1, string text2) {
    vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
    for (int i = 1; i <= text1.size(); ++i) {
        for (int j = 1; j <= text2.size(); ++j) {
            if (text1[i - 1] == text2[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[text1.size()][text2.size()];
}


int main()
{   
    string str1 = "abac";
    string str2 = "cab";

    int lcs_length = lcs_bottom_up(str1, str2);

    cout << "Shortest common super sequence length = "<<(str1.size() + str2.size() - lcs_length)<<endl;
  
}

Output:

Shortest common super sequence length = 5