Longest Common Substring in DSA C - Execution Trace

Concept Flow - Longest Common Substring

Start with two strings

↓

Create 2D table of size (len1+1) x (len2+1)

↓

Initialize all cells to 0

↓

For each character pair (i,j)

↓

If chars match: table[i

↓

Update max length and position if needed

↓

After filling table, extract substring from max position

↓

Return longest common substring

↓

Done

We build a table to track matching characters between two strings, updating lengths of common substrings and remembering the longest found.

Execution Sample

DSA C

char* longestCommonSubstring(char* s1, char* s2) {
  int len1 = strlen(s1), len2 = strlen(s2);
  int table[len1+1][len2+1];
  int maxLen = 0, endPos = 0;
  for (int i = 0; i <= len1; i++)
    for (int j = 0; j <= len2; j++)
      table[i][j] = 0;
  for (int i = 1; i <= len1; i++) {
    for (int j = 1; j <= len2; j++) {
      if (s1[i-1] == s2[j-1]) {
        table[i][j] = table[i-1][j-1] + 1;
        if (table[i][j] > maxLen) {
          maxLen = table[i][j];
          endPos = i;
        }
      } else {
        table[i][j] = 0;
      }
    }
  }
  char* result = malloc(maxLen + 1);
  strncpy(result, s1 + endPos - maxLen, maxLen);
  result[maxLen] = '\0';
  return result;
}

This code finds the longest substring common to both input strings by building a table of matching character lengths.

Execution Table

Step	Operation	Indices (i,j)	Chars Compared	Table[i][j]	Max Length	End Position	Visual State (Table snippet)
1	Initialize table	-	-	-	0	0	All zeros
2	Compare chars	(1,1)	'a' vs 'b'	0	0	0	table[1][1]=0
3	Compare chars	(1,2)	'a' vs 'a'	1	1	1	table[1][2]=1
4	Compare chars	(1,3)	'a' vs 'c'	0	1	1	table[1][3]=0
5	Compare chars	(2,1)	'b' vs 'b'	1	1	1	table[2][1]=1
6	Compare chars	(2,2)	'b' vs 'a'	0	1	1	table[2][2]=0
7	Compare chars	(2,3)	'b' vs 'c'	0	1	1	table[2][3]=0
8	Compare chars	(3,1)	'c' vs 'b'	0	1	1	table[3][1]=0
9	Compare chars	(3,2)	'c' vs 'a'	0	1	1	table[3][2]=0
10	Compare chars	(3,3)	'c' vs 'c'	1	1	1	table[3][3]=1
11	Compare chars	(4,1)	'd' vs 'b'	0	1	1	table[4][1]=0
12	Compare chars	(4,2)	'd' vs 'a'	0	1	1	table[4][2]=0
13	Compare chars	(4,3)	'd' vs 'c'	0	1	1	table[4][3]=0
14	Compare chars	(5,1)	'e' vs 'b'	0	1	1	table[5][1]=0
15	Compare chars	(5,2)	'e' vs 'a'	0	1	1	table[5][2]=0
16	Compare chars	(5,3)	'e' vs 'c'	0	1	1	table[5][3]=0
17	End of loops	-	-	-	1	1	Longest substring length=1, ends at s1 index 1
18	Extract substring	-	-	-	-	-	Substring: 'a'

💡 All character pairs compared; longest common substring length found and extracted.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 10	After Step 17	Final
maxLen	0	1	1	1	1	1
endPos	0	1	1	1	1	1
table[1][2]	0	1	1	1	1	1
table[2][1]	0	0	1	1	1	1
table[3][3]	0	0	0	1	1	1

Key Moments - 3 Insights

Why do we start filling the table from index 1 instead of 0?

Because table[0][*] and table[*][0] represent empty prefixes, initialized to zero to handle boundary cases. See execution_table rows 2-3 where i and j start at 1.

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

Because a matching character extends the previous common substring by one. This is shown in execution_table row 3 where table[1][2] = table[0][1] + 1 = 1.

How do we know which substring is the longest after filling the table?

We track maxLen and endPos during filling. The longest substring ends at endPos in s1 with length maxLen, as shown in execution_table row 17.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the value of table[1][2] and what does it represent?

A 2, sum of previous matches

B 0, no match at these indices

C 1, length of common substring ending at s1[0] and s2[1]

D Undefined, not calculated yet

💡 Hint

Refer to execution_table row 3 under 'Table[i][j]' and 'Chars Compared'

At which step does the algorithm update maxLen for the first time?

A Step 2

B Step 3

C Step 5

D Step 10

💡 Hint

Check execution_table rows where maxLen changes from 0 to 1

If the input strings were 'abc' and 'abc', what would be the maxLen after filling the table?

A 3

B 1

C 2

D 0

💡 Hint

Longest common substring length equals the full string length if both strings are identical

Concept Snapshot

Longest Common Substring:
- Use 2D table of size (len1+1) x (len2+1)
- Initialize all cells to 0
- For each i,j: if s1[i-1]==s2[j-1], table[i][j] = table[i-1][j-1] + 1
- Track max length and end position
- Extract substring from s1 using end position and max length

Full Transcript

The Longest Common Substring algorithm compares two strings by building a 2D table. Each cell table[i][j] stores the length of the longest common substring ending at s1[i-1] and s2[j-1]. We initialize the table with zeros. For each character pair, if they match, we add 1 to the value from the previous diagonal cell. We keep track of the maximum length found and the position where it ends in s1. After filling the table, we extract the substring from s1 using the recorded position and length. This method efficiently finds the longest substring shared by both strings.

Practice

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

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 the two strings

D. The longest string formed by concatenating 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 breaks (consecutively).

2. Step 2: Differentiate from similar problems

   Unlike Longest Common Subsequence, which allows characters to be non-consecutive, Longest Common Substring requires consecutive matching characters.

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 consecutive matching characters in both strings [OK]

Common Mistakes:

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

2. Which of the following C code snippets correctly initializes a 2D array dp of size m+1 by n+1 with all zeros for Longest Common Substring?

easy

A. int dp[m+1][n+1] = {0};

B. int dp[m+1][n+1]; memset(dp, 0, sizeof(dp));

C. int dp[m][n]; for(int i=0;i

D. int dp[m+1][n+1]; for(int i=0;i<=m;i++) for(int j=0;j<=n;j++) dp[i][j] = -1;

Solution

1. Step 1: Understand array initialization in C

   To initialize a 2D array with zeros, we can declare it and then use memset to set all bytes to zero.

2. Step 2: Analyze each option

   int dp[m+1][n+1] = {0}; tries to initialize with {0} but this only works for fixed size arrays, not variable sizes. int dp[m+1][n+1]; memset(dp, 0, sizeof(dp)); declares and uses memset correctly. int dp[m][n]; for(int i=0;i

3. Final Answer:

   int dp[m+1][n+1]; memset(dp, 0, sizeof(dp)); -> Option B

4. Quick Check:

   Use memset to zero initialize arrays in C [OK]

Hint: Use memset to zero initialize arrays in C [OK]

Common Mistakes:

• Using {0} for variable size arrays
• Initializing with wrong values like 1 or -1
• Not initializing dp array before use

3. What is the output of the following C code snippet that finds the length of the longest common substring between s1 = "abcde" and s2 = "abfde"?

int longestCommonSubstring(char* s1, char* s2) {
    int m = strlen(s1), n = strlen(s2);
    int dp[m+1][n+1];
    memset(dp, 0, sizeof(dp));
    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;
            }
        }
    }
    return maxLen;
}

int main() {
    printf("%d", longestCommonSubstring("abcde", "abfde"));
    return 0;
}

medium

A. 2

B. 3

C. 4

D. 5

Solution

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

   Strings: s1 = "abcde", s2 = "abfde". Matching consecutive characters are "ab" at start and "de" at end. "ab" length = 2, "de" length = 2. The longest common substring length is 2.

2. Step 2: Check dp updates for longest substring

   At i=3, j=3, characters differ ('c' vs 'f'), so dp resets. The longest substring is "ab" or "de" with length 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Longest Common Substring length = 2 [OK]

Hint: Check consecutive matching chars, reset on mismatch [OK]

Common Mistakes:

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

4. The following code attempts to find the longest common substring length but has a bug. What is the bug?

int longestCommonSubstring(char* s1, char* s2) {
    int m = strlen(s1), n = strlen(s2);
    int dp[m][n];
    int maxLen = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (s1[i] == s2[j]) {
                dp[i][j] = dp[i-1][j-1] + 1;
                if (dp[i][j] > maxLen) maxLen = dp[i][j];
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return maxLen;
}

medium

A. dp array is not initialized before use

B. The loop indices should start from 1 instead of 0

C. The maxLen variable is not updated correctly

D. dp array size should be (m+1) x (n+1) to avoid out-of-bound access

Solution

1. Step 1: Analyze dp array size and indexing

   The dp array is declared as dp[m][n], but the code accesses dp[i-1][j-1] which can cause out-of-bound access when i=0 or j=0.

2. Step 2: Correct dp array size and indexing

   To safely access dp[i-1][j-1], dp should be sized (m+1) x (n+1) and loops should run from 1 to m and 1 to n, with dp[0][*] and dp[*][0] initialized to 0.

3. Final Answer:

   dp array size should be (m+1) x (n+1) to avoid out-of-bound access -> Option D

4. Quick Check:

   Use dp size (m+1)x(n+1) for safe indexing [OK]

Hint: Use dp size (m+1)x(n+1) to avoid negative indices [OK]

Common Mistakes:

• Using dp size m x n causing index errors
• Starting loops at 0 but accessing dp[i-1][j-1]
• Not initializing dp array elements

5. Given two strings s1 = "banana" and s2 = "ananas", write a C function to find the longest common substring and return its length. What is the length of the longest common substring?

hard

A. 5

B. 4

C. 3

D. 6

Solution

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

   Check substrings of s1 and s2. Common substrings include "ana", "nan", "ana" again, and the longest is "ana" with length 3.

2. Step 2: Confirm no longer substring exists

   No substring longer than 3 exists in both strings consecutively. "anana" is not a substring of "banana" starting at index 1 (it's "anana" in s2 but not in s1 consecutively).

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Longest common substring between "banana" and "ananas" is "ana" length 3 [OK]

Hint: Look for "ana" substring in both strings [OK]

Common Mistakes:

• Confusing substring with subsequence
• Assuming "anana" is common substring
• Stopping at shorter matches like "an"