Longest Common Substring in DSA C# - Execution Trace

Concept Flow - Longest Common Substring

Start with two strings

↓

Create 2D table of size (m+1)x(n+1)

↓

Initialize all cells to 0

↓

For each character in string1 (i)

↓

For each character in string2 (j)

↓

If chars match: table[i

↓

Update max length and position if needed

↓

After filling table, extract substring from string1

↓

Return longest common substring

↓

End

We compare characters of both strings using a 2D table to find the longest matching substring by building lengths step-by-step.

Execution Sample

DSA C#

string s1 = "abcde";
string s2 = "abfde";
int[,] dp = new int[s1.Length + 1, s2.Length + 1];
int maxLen = 0, endIndex = 0;
// Fill dp table and track max substring

This code builds a table to find the longest common substring between s1 and s2.

Execution Table

Step	Operation	i	j	Chars Compared	dp[i,j]	Max Length	End Index	Visual State (dp table snapshot)
1	Initialize dp table	-	-	-	All zeros	0	0	[[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
2	Compare s1[0]='a' and s2[0]='a'	1	1	'a' == 'a'	1	1	1	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
3	Compare s1[0]='a' and s2[1]='b'	1	2	'a' != 'b'	0	1	1	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
4	Compare s1[0]='a' and s2[2]='f'	1	3	'a' != 'f'	0	1	1	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
5	Compare s1[0]='a' and s2[3]='d'	1	4	'a' != 'd'	0	1	1	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
6	Compare s1[0]='a' and s2[4]='e'	1	5	'a' != 'e'	0	1	1	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
7	Compare s1[1]='b' and s2[0]='a'	2	1	'b' != 'a'	0	1	1	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
8	Compare s1[1]='b' and s2[1]='b'	2	2	'b' == 'b'	2	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
9	Compare s1[1]='b' and s2[2]='f'	2	3	'b' != 'f'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
10	Compare s1[1]='b' and s2[3]='d'	2	4	'b' != 'd'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
11	Compare s1[1]='b' and s2[4]='e'	2	5	'b' != 'e'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
12	Compare s1[2]='c' and s2[0]='a'	3	1	'c' != 'a'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
13	Compare s1[2]='c' and s2[1]='b'	3	2	'c' != 'b'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
14	Compare s1[2]='c' and s2[2]='f'	3	3	'c' != 'f'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
15	Compare s1[2]='c' and s2[3]='d'	3	4	'c' != 'd'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
16	Compare s1[2]='c' and s2[4]='e'	3	5	'c' != 'e'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
17	Compare s1[3]='d' and s2[0]='a'	4	1	'd' != 'a'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
18	Compare s1[3]='d' and s2[1]='b'	4	2	'd' != 'b'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
19	Compare s1[3]='d' and s2[2]='f'	4	3	'd' != 'f'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
20	Compare s1[3]='d' and s2[3]='d'	4	4	'd' == 'd'	1	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,1,0,0],[0,0,0,0,0,0]]
21	Compare s1[3]='d' and s2[4]='e'	4	5	'd' != 'e'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,1,0,0],[0,0,0,0,0,0]]
22	Compare s1[4]='e' and s2[0]='a'	5	1	'e' != 'a'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,1,0,0],[0,0,0,0,0,0]]
23	Compare s1[4]='e' and s2[1]='b'	5	2	'e' != 'b'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,1,0,0],[0,0,0,0,0,0]]
24	Compare s1[4]='e' and s2[2]='f'	5	3	'e' != 'f'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,1,0,0],[0,0,0,0,0,0]]
25	Compare s1[4]='e' and s2[3]='d'	5	4	'e' != 'd'	0	2	2	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,1,0,0],[0,0,0,0,0,0]]
26	Compare s1[4]='e' and s2[4]='e'	5	5	'e' == 'e'	2	2	5	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,2,0,0,0],[0,0,0,0,0,0],[0,0,0,1,0,0],[0,0,0,0,0,2]]
27	End of loops	-	-	-	-	2	5	Final dp table filled

💡 All characters compared, longest common substring length found is 2 ending at index 5 in s1

Variable Tracker

Variable	Start	After Step 2	After Step 8	After Step 20	After Step 26	Final
maxLen	0	1	2	2	2	2
endIndex	0	1	2	2	5	5
dp[1,1]	0	1	1	1	1	1
dp[2,2]	0	0	2	2	2	2
dp[4,4]	0	0	0	1	1	1
dp[5,5]	0	0	0	0	2	2

Key Moments - 3 Insights

Why do we add 1 to dp[i-1][j-1] when characters match?

Because dp[i-1][j-1] stores the length of the longest common substring ending at previous characters, so adding 1 extends it by one matching character (see steps 2, 8, 26).

Why do we reset dp[i,j] to 0 when characters don't match?

Because the substring must be continuous, so no match means no extension; dp[i,j] is zero to indicate no common substring ending here (see steps 3, 9, 19).

How do we know where the longest substring ends?

We track the endIndex whenever maxLen updates (see steps 8 and 26), so after filling the table, endIndex points to the last character of the longest substring in s1.

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the value of dp[2,2]?

A 2

B 1

C 0

D 3

💡 Hint

Check the 'dp[i,j]' column at step 8 in the execution_table.

At which step does maxLen first become 2?

A Step 2

B Step 20

C Step 8

D Step 26

💡 Hint

Look at the 'Max Length' column in execution_table rows to find when it changes to 2.

If s1[4] was 'f' instead of 'e', how would dp[5,5] change at step 26?

A It would be 2

B It would be 0

C It would be 1

D It would be 3

💡 Hint

Since characters don't match, dp[i,j] resets to 0 (see steps where chars differ).

Concept Snapshot

Longest Common Substring:
- Use 2D dp table of size (m+1)x(n+1)
- dp[i,j] = dp[i-1,j-1] + 1 if s1[i-1] == s2[j-1], else 0
- Track max length and end index
- Extract substring from s1 using end index and max length
- Finds longest continuous matching substring

Full Transcript

Longest Common Substring finds the longest continuous substring common to two strings. We create a 2D table where each cell dp[i,j] represents the length of the longest common substring ending at s1[i-1] and s2[j-1]. If characters match, we add 1 to dp[i-1,j-1], else reset to 0. We track the maximum length and the position where it ends. After filling the table, we extract the substring from s1 using the recorded end index and max length. This method ensures we find the longest continuous matching substring efficiently.

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