Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in C#

Solution: Shortest Common Supersequence (SCS)

Understand multiple dynamic programming techniques to solve the Shortest Common Supersequence problem. Learn brute force recursion, optimize with memoization, and apply tabularization to achieve efficient solutions with clear time and space complexity analyses.

We'll cover the following...

Solution 1: Brute force

C#
using System;
class Program
{
    /// <summary>
    /// Finds the length of the shortest common supersequence.
    /// </summary>
    /// <param name="s1">First string.</param>
    /// <param name="s2">Second string.</param>
    /// <param name="i1">Starting index of substring.</param>
    /// <param name="i2">Ending index of substring.</param>
    /// <returns>Length of shortest common supersequence.</returns>
    static int ShortestCommonSupersequenceRecursive(string s1, string s2, int i1, int i2)
    {
        if (i1 == s1.Length)
            return s2.Length - i2;
        if (i2 == s2.Length)
            return s1.Length - i1;
        if (s1[i1] == s2[i2])
            return 1 + ShortestCommonSupersequenceRecursive(s1, s2, i1 + 1, i2 + 1);
        
        int length1 = 1 + ShortestCommonSupersequenceRecursive(s1, s2, i1, i2 + 1);
        int length2 = 1 + ShortestCommonSupersequenceRecursive(s1, s2, i1 + 1, i2);
        return Math.Min(length1, length2);
    }
    /// <summary>
    /// Finds the length of the shortest common supersequence.
    /// </summary>
    /// <param name="s1">First string.</param>
    /// <param name="s2">Second string.</param>
    /// <returns>Length of shortest common supersequence.</returns>
    public static int ShortestCommonSupersequence(string s1, string s2)
    {
        return ShortestCommonSupersequenceRecursive(s1, s2, 0, 0);
    }
    // Driver code to test the above method
    public static void Main()
    {
        Console.WriteLine(ShortestCommonSupersequence("abcdz", "bdcf"));
        Console.WriteLine(ShortestCommonSupersequence("educative", "educative.io"));
    }
}

Explanation

In this solution, we try all the superstrings—one character at a time.

  • If the sequences have a matching i-th character, we skip one character from both the sequences and make a recursive call for the remaining lengths (lines 20–21).
  • If the characters don’t match, we call the function recursively twice by skipping one character from each string (lines 23–24).
  • We return the minimum result of these two calls (line 26).

Time complexity

The time complexity of the above algorithm is exponential O(2n+m)O(2^{n+m}), where nn ...