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

Solution: Longest Common Substring

Learn to solve the longest common substring problem using multiple dynamic programming approaches in C#. Discover how brute force, memoization, and tabulation methods work, analyze their time and space complexities, and improve performance by optimizing space usage in solutions.

We'll cover the following...

Solution 1: Brute force

C# 9.0
using System;
class Program
{
    /// <summary>
    /// Finds the length of the longest common substring.
    /// </summary>
    /// <param name="s1">First string.</param>
    /// <param name="s2">Second string.</param>
    /// <returns>Length of longest common substring.</returns>
    public static int LongestCommonSubstrLength(string s1, string s2)
    {
        return LongestCommonSubstrLengthRecursive(s1, s2, 0, 0, 0);
    }
    /// <summary>
    /// Finds the length of the longest common substring.
    /// </summary>
    /// <param name="s1">First string.</param>
    /// <param name="s2">Second string.</param>
    /// <param name="i1">Current index in s1.</param>
    /// <param name="i2">Current index in s2.</param>
    /// <param name="count">Current length of common substring.</param>
    /// <returns>Length of longest common substring.</returns>
    static int LongestCommonSubstrLengthRecursive(string s1, string s2, int i1, int i2, int count)
    {
        if (i1 == s1.Length || i2 == s2.Length)
        {
            return count;
        }
        if (s1[i1] == s2[i2])
        {
            return LongestCommonSubstrLengthRecursive(s1, s2, i1 + 1, i2 + 1, count + 1);
        }
        else
        {
            int c1 = LongestCommonSubstrLengthRecursive(s1, s2, i1, i2 + 1, 0);
            int c2 = LongestCommonSubstrLengthRecursive(s1, s2, i1 + 1, i2, 0);
            return Math.Max(count, Math.Max(c1, c2));
        }
    }
    // Driver code to test the above method
    static void Main()
    {
        string S1 = "0abc321";
        string S2 = "123abcdef";
        Console.WriteLine(LongestCommonSubstrLength(S1, S2));
        // Uncomment below to test with other strings
        // S1 = "www.educative.io/explore";
        // S2 = "educative.io/edpresso";
        // Console.WriteLine(LongestCommonSubstrLength(S1, S2));
    }
}

Explanation

This is a naive solution that finds all the substrings of the two given strings and then discovers the longest common substrings between the two.

If the strings have a matching character, we recursively check for the remaining length of each and keep a track of the current matching length.

If the characters don’t match, we start two new recursive calls by skipping those characters from each string.

The length of the longest common substring will be the maximum number returned by the three recursive calls.

Time complexity

The time complexity of the above code is O(2n+m)O(2^{n+m}).

The space complexity is O(m+n)O(m+n) ...