Longest Common Substring in DSA C#

Mental Model

Find the longest sequence of characters that appears exactly the same in both strings without skipping any characters.

Analogy: Imagine two friends reading two different books and trying to find the longest exact sentence that appears in both books without any changes or breaks.

String1: a b c d e f g h
String2: x y c d e z

We look for the longest continuous matching part: c d e

Dry Run Walkthrough

Input: string1: "abcde", string2: "abfde"

Goal: Find the longest substring that appears in both strings exactly and continuously

Step 1: Compare first characters 'a' and 'a', they match, start substring length 1

Match at indices (0,0): substring length = 1

Why: We found a matching start for a common substring

Step 2: Compare next characters 'b' and 'b', they match, substring length increases to 2

Match at indices (1,1): substring length = 2

Why: Continuing the matching substring

Step 3: Compare 'c' and 'f', no match, reset substring length to 0

Mismatch at indices (2,2): substring length reset to 0

Why: Mismatch breaks the continuous substring

Step 4: Compare 'd' and 'd', match, substring length = 1

Match at indices (3,3): substring length = 1

Why: New matching substring starts

Step 5: Compare 'e' and 'e', match, substring length = 2

Match at indices (4,4): substring length = 2

Why: Continuing the matching substring

Result:

Longest common substring length = 2, substring = "ab" or "de"

Annotated Code

DSA C#

using System;

class LongestCommonSubstring
{
    public static string FindLongestCommonSubstring(string s1, string s2)
    {
        int maxLen = 0;
        int endIndexS1 = 0;
        int[,] dp = new int[s1.Length + 1, s2.Length + 1];

        for (int i = 1; i <= s1.Length; i++)
        {
            for (int j = 1; j <= s2.Length; j++)
            {
                if (s1[i - 1] == s2[j - 1])
                {
                    dp[i, j] = dp[i - 1, j - 1] + 1; // extend previous substring
                    if (dp[i, j] > maxLen)
                    {
                        maxLen = dp[i, j];
                        endIndexS1 = i - 1; // track end index of substring in s1
                    }
                }
                else
                {
                    dp[i, j] = 0; // reset on mismatch
                }
            }
        }

        if (maxLen == 0) return "";
        return s1.Substring(endIndexS1 - maxLen + 1, maxLen);
    }

    static void Main()
    {
        string s1 = "abcde";
        string s2 = "abfde";
        string result = FindLongestCommonSubstring(s1, s2);
        Console.WriteLine(result);
    }
}

if (s1[i - 1] == s2[j - 1])

Check if characters match to continue substring

dp[i, j] = dp[i - 1, j - 1] + 1; // extend previous substring

Extend length of current matching substring by 1

if (dp[i, j] > maxLen)

Update max length and end index if current substring is longer

dp[i, j] = 0; // reset on mismatch

Reset substring length when characters do not match

return s1.Substring(endIndexS1 - maxLen + 1, maxLen);

Extract the longest common substring from s1

Output

ab

Complexity Analysis

Time: O(m*n) because we compare each character of string1 with each character of string2 once

Space: O(m*n) because we use a 2D array to store substring lengths for all pairs of indices

vs Alternative: Naive approach checks all substrings which is O(m^2*n^2), this dynamic programming approach is much faster

Edge Cases

One or both strings empty

Returns empty string as no common substring exists

DSA C#

if (maxLen == 0) return "";

No common substring

Returns empty string

DSA C#

if (maxLen == 0) return "";

Strings are identical

Returns the entire string as longest common substring

DSA C#

dp[i, j] = dp[i - 1, j - 1] + 1;

When to Use This Pattern

When asked to find the longest exact continuous matching part between two strings, use the Longest Common Substring pattern with dynamic programming to efficiently track matching lengths.

Common Mistakes

Mistake: Confusing longest common substring with longest common subsequence (which allows skipping characters)
Fix: Remember substring requires continuous characters; reset count on mismatch

Mistake: Not resetting dp value to zero on mismatch, causing incorrect substring lengths
Fix: Set dp[i, j] = 0 when characters do not match

Summary

Finds the longest continuous sequence of characters common to both strings.

Use when you need the longest exact matching substring between two strings.

The key is to build lengths of matching substrings step-by-step and reset on mismatch.

Practice

1. What does the Longest Common Substring problem find between two strings?

easy

A. The longest sequence of characters that appear consecutively in both strings

B. The longest sequence of characters that appear anywhere in both strings, not necessarily consecutively

C. The total number of common characters between two strings

D. The longest string formed by combining both strings

Solution

1. Step 1: Understand the problem definition

   The Longest Common Substring problem looks for the longest sequence of characters that appear in both strings without any gaps.

2. Step 2: Differentiate from similar problems

   Unlike Longest Common Subsequence, substrings must be continuous in both strings.

3. Final Answer:

   The longest sequence of characters that appear consecutively in both strings -> Option A

4. Quick Check:

   Longest Common Substring = consecutive matching characters [OK]

Hint: Look for continuous matching characters in both strings [OK]

Common Mistakes:

• Confusing substring with subsequence
• Thinking characters can be non-continuous
• Counting total common characters instead of longest sequence

2. Which of the following C# code snippets correctly initializes a 2D array for dynamic programming in Longest Common Substring?

easy

A. int[][] dp = new int[m][n];

B. int[,] dp = new int[m][n];

C. int[,] dp = new int[m + 1, n + 1];

D. int[][] dp = new int[m + 1, n + 1];

Solution

1. Step 1: Recall C# syntax for 2D arrays

   In C#, a rectangular 2D array is declared as int[,] with sizes specified in new int[m + 1, n + 1].

2. Step 2: Check each option

   int[,] dp = new int[m + 1, n + 1]; uses correct syntax. Options A and D mix jagged and rectangular array syntax incorrectly. int[,] dp = new int[m][n]; uses wrong initialization syntax.

3. Final Answer:

   int[,] dp = new int[m + 1, n + 1]; -> Option C

4. Quick Check:

   Rectangular 2D array syntax = int[,] dp = new int[m + 1, n + 1]; [OK]

Hint: Use int[,] for 2D arrays, not jagged arrays for DP [OK]

Common Mistakes:

• Using jagged array syntax incorrectly
• Missing +1 for boundary conditions
• Mixing rectangular and jagged array syntax

3. What is the output of the following C# code snippet?

string s1 = "abcde";
string s2 = "abfde";
int m = s1.Length;
int n = s2.Length;
int[,] dp = new int[m + 1, n + 1];
int maxLen = 0;
for (int i = 1; i <= m; i++) {
  for (int j = 1; j <= n; j++) {
    if (s1[i - 1] == s2[j - 1]) {
      dp[i, j] = dp[i - 1, j - 1] + 1;
      if (dp[i, j] > maxLen) maxLen = dp[i, j];
    } else {
      dp[i, j] = 0;
    }
  }
}
Console.WriteLine(maxLen);

medium

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Trace matching characters between s1 and s2

   Strings: s1 = "abcde", s2 = "abfde". Matching substrings are "ab" at start and "de" at end, both length 2.

2. Step 2: Identify longest common substring length

   Longest common substring length is 2, either "ab" or "de".

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Longest common substring length = 2 [OK]

Hint: Check continuous matching chars, not total matches [OK]

Common Mistakes:

• Counting non-continuous matches
• Confusing substring length with subsequence length
• Off-by-one errors in indexing

4. Identify the bug in this Longest Common Substring C# code snippet:

string s1 = "hello";
string s2 = "yellow";
int m = s1.Length;
int n = s2.Length;
int[,] dp = new int[m, n];
int maxLen = 0;
for (int i = 1; i <= m; i++) {
  for (int j = 1; j <= n; j++) {
    if (s1[i - 1] == s2[j - 1]) {
      dp[i, j] = dp[i - 1, j - 1] + 1;
      if (dp[i, j] > maxLen) maxLen = dp[i, j];
    } else {
      dp[i, j] = 0;
    }
  }
}
Console.WriteLine(maxLen);

medium

A. The comparison should be s1[i] == s2[j] without -1

B. The dp array size should be (m+1, n+1) to avoid index errors

C. The loops should start from 0 instead of 1

D. maxLen should be initialized to -1

Solution

1. Step 1: Check dp array size and indexing

   dp is declared as int[m, n], but loops access dp[i, j] with i and j up to m and n, causing index out of range.

2. Step 2: Correct dp size for safe indexing

   dp should be int[m+1, n+1] to allow indices from 0 to m and 0 to n safely.

3. Final Answer:

   The dp array size should be (m+1, n+1) to avoid index errors -> Option B

4. Quick Check:

   dp size = (m+1, n+1) for safe indexing [OK]

Hint: Add +1 to dp array size for boundary indexing [OK]

Common Mistakes:

• Using dp size without +1 causes runtime errors
• Starting loops at 0 causes negative indexing
• Incorrect character indexing without -1

5. Given two strings s1 = "xabxac" and s2 = "abcabxabcd", what is the length of their longest common substring?

hard

A. 3

B. 6

C. 5

D. 4

Solution

1. Step 1: Identify common substrings between s1 and s2

   Check substrings like "abx", "bxa", "xab", "abxa". The longest common substring is "abxa" with length 4.

2. Step 2: Confirm no longer substring exists

   "abxac" is in s1 but not fully in s2 consecutively. So length 4 is maximum.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Longest common substring length = 4 [OK]

Hint: Look for longest continuous matching sequence [OK]

Common Mistakes:

• Counting subsequence instead of substring
• Overestimating length by including non-continuous chars
• Ignoring overlapping substrings