Longest Common Substring in DSA C# - Build from Scratch

Longest Common Substring

📖 Scenario: You are working on a text comparison tool that helps find the longest matching part between two texts. This is useful in plagiarism detection, DNA sequence analysis, or finding common phrases.

🎯 Goal: Build a program that finds the longest common substring between two given strings.

📋 What You'll Learn

Create two string variables with exact given values

Create a 2D integer array to store lengths of common suffixes

Use nested loops to fill the 2D array and track the longest substring length and position

Extract and print the longest common substring

💡 Why This Matters

🌍 Real World

Finding longest common substrings is useful in text comparison tools, DNA sequence analysis, and plagiarism detection.

💼 Career

Understanding dynamic programming and string algorithms is important for software development roles involving data processing, bioinformatics, and search engines.

1

Create the input strings

Create two string variables called str1 and str2 with the exact values "ABABC" and "BABCA" respectively.

DSA C#

# Your code here

Hint

Use string type and assign the exact text inside double quotes.

2

Create the 2D array and helper variables

Create a 2D integer array called dp with dimensions str1.Length + 1 by str2.Length + 1. Also create two integer variables called maxLength and endIndex and set both to 0.

DSA C#

string str1 = "ABABC";
string str2 = "BABCA";
# Your code here

Hint

Use new int[rows, columns] to create the 2D array. Initialize maxLength and endIndex to zero.

3

Fill the 2D array and find longest substring

Use nested for loops with variables i from 1 to str1.Length and j from 1 to str2.Length. Inside, check if str1[i - 1] equals str2[j - 1]. If yes, set dp[i, j] = dp[i - 1, j - 1] + 1. If dp[i, j] is greater than maxLength, update maxLength to dp[i, j] and endIndex to i.

DSA C#

string str1 = "ABABC";
string str2 = "BABCA";
int[,] dp = new int[str1.Length + 1, str2.Length + 1];
int maxLength = 0;
int endIndex = 0;
# Your code here

Hint

Use two loops to compare characters. Update dp and track the longest substring length and position.

4

Extract and print the longest common substring

Create a string variable called longestSubstring by extracting the substring from str1 starting at endIndex - maxLength with length maxLength. Then print longestSubstring.

DSA C#

string str1 = "ABABC";
string str2 = "BABCA";
int[,] dp = new int[str1.Length + 1, str2.Length + 1];
int maxLength = 0;
int endIndex = 0;

for (int i = 1; i  maxLength)
            {
                maxLength = dp[i, j];
                endIndex = i;
            }
        }
    }
}
# Your code here

Hint

Use Substring method on str1 with start index endIndex - maxLength and length maxLength. Then print the result.

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