Grokking Dynamic Programming Interview/

...

/

Shortest Common Supersequence

Shortest Common Supersequence

Let's solve the Shortest Common Supersequence problem using Dynamic Programming.

We'll cover the following...

Statement

Given two strings, str1 and str2, find the length of the shortest string that has both the input strings as subsequences.

Note: A string XX is a subsequence of string YY if deleting some number of characters from YY results in the string XX.

Let’s assume that we have two strings as follows:

  • str1 = "yabc"
  • str2 = "xabc"

There can be multiple strings that have str1 and str2 as subsequences, for example, "xyaabcc" and "xyabbc", but the shortest string that has these input strings as subsequences is "xyabc". Please note that the sequence of alphabets in the string can be altered.

Constraints:

  • 1≤1 \leq str1.length, str2.length ≤2700\leq 2700
  • str1 and str2 consist of lowercase English letters.

Examples

No.

str1

str2

Length of Shortest Common Supersequence

1

"bcf"

"bdcf"

4

2

"dynamic"

"programming"

15

Try it yourself

Implement your solution in the following playground.

Press + to interact
Java
usercode > Main.java
public class Main {

    public static int shortestCommonSupersequence(String str1, String str2) {

        // your code will replace the placeholder return statement below

        return -1;

    }

};
Shortest Common Supersequence

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach

A naive approach is to try all the supersequences, one character at a time.

The two changing parameters in our recursive function are the two indices, i1 and i2 which are incremented based on the following two conditions:

  • If the characters at i1 and i2 are a match, skip one character from both the sequences and make a recursive call for the remaining lengths.
  • If the characters do not match, call the function recursively twice by skipping one character from each string. Return the minimum result of these two calls.

Let’s implement the algorithm as discussed above:

import java.util.*;
import java.util.stream.*;
class ShortestCommonSUpersequence {
    public static int shortestCommonSupersequenceRecursive(String str1, String str2, int i1, int i2) {
        // if any of the pointers has iterated over all the characters of the string,
        // return the remaining length of the other string 
        if (i1 == str1.length()) {
            return str2.length() - i2;
        }
        if (i2 == str2.length()) {
            return str1.length() - i1;
        }
        // if both the characters pointed by i1 and i2 are same, increment both pointers
        if (str1.charAt(i1) == str2.charAt(i2)) {
            return 1 + shortestCommonSupersequenceRecursive(str1, str2, i1 + 1, i2 + 1);
        }
        // recursively call the function twice by skipping one character from each string
        int length1 = 1 + shortestCommonSupersequenceRecursive(str1, str2, i1, i2 + 1);
        int length2 = 1 + shortestCommonSupersequenceRecursive(str1, str2, i1 + 1, i2);
        
        // return the minimum of the two lengths
        return Math.min(length1, length2);
    }
    public static int shortestCommonSupersequence(String str1, String str2) {
        return shortestCommonSupersequenceRecursive(str1, str2, 0, 0);
    }
    // driver code
    public static void main(String[] arg) {
        String[] input1Strings = {"abcd", "educativeisfun", "cpprocks", "abcf", "dynamic"};
        String[] input2Strings = {"efgh", "algorithmsarefun", "cppisfun", "bdcf", "programming"};
        // you can uncomment the lines below and check how this recursive solution causes a time-out
        
        // String newArr[] = Arrays.copyOf(input1Strings, input1Strings.length + 1);
        // newArr[input1Strings.length] = "iloveprogrammingbutprogrammingdoesnotloveme";
        // input1Strings = newArr;
        // newArr = Arrays.copyOf(input2Strings, input2Strings.length + 1);
        // newArr[input2Strings.length] = "computersarefastprogrammerskeepthemslow";
        // input2Strings = newArr;
        for (int i = 0; i < input1Strings.length; i++) {
            System.out.print(i + 1);
            System.out.println("\tString 1: " + input1Strings[i]);
            System.out.println("\tString 1: " + input2Strings[i]);
            System.out.println("\tLength of Shortest Common Supersequence: " + shortestCommonSupersequence(input1Strings[i], input2Strings[i]));
            Stream.generate(() -> "-").limit(100).forEach(System.out::print);
            System.out.println();
        }
    }
};
Shortest Common Supersequence using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity

The time complexity of the naive approach is exponential O ...