Challenge: Shortest Common Supersequence

Problem Statement

Given two strings, write a function to find the length of their shortest common superstring or “supersequence”. A superstring is a string which has both input strings as substrings.

Input

Two strings

Output

The length of their shortest common supersequence

Sample Input

string s1 = "abcf";
string s2 = "bdcf";

Sample Output

5 // The SCS is "abdcf"

Coding Exercise

Take a close look and design a step-by-step algorithm before jumping on to the implementation. This problem is designed for your practice, so try to solve it on your own first. If you get stuck, you can always refer to the hint and solution provided in the code tab. Good Luck!