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 sentences written on paper. The longest common substring is like the longest exact phrase that appears in both sentences side by side without any gaps.

String1: A B C D E F G
String2: X Y B C D Z

We look for the longest exact matching block:
B -> C -> D
↑          ↑
match starts here

Dry Run Walkthrough

Input: String1: "ABCDXYZ", String2: "XYZABCD"

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

Step 1: Initialize a 2D array dp with zeros for lengths of substrings

dp matrix filled with 0s, size 8x8 (including empty prefix)

Why: We need a table to store lengths of matching substrings ending at each pair of indices

Step 2: Compare characters at String1[1] = 'A' and String2[1] = 'X', no match, dp[1][1] = 0

dp[1][1] = 0

Why: No common substring ends here because characters differ

Step 3: Compare String1[4] = 'D' and String2[7] = 'D', match found, dp[4][7] = dp[3][6] + 1 = 4

dp[4][7] = 4 (substring length 4 ending here)

Why: We extend the previous matching substring by 1 character

Step 4: Update max length to 4 and record ending index in String1

max_len = 4, end_index = 4

Why: Keep track of the longest substring found so far

Result:

Longest common substring length = 4, substring = "ABCD"

Annotated Code

DSA C

#include <stdio.h>
#include <string.h>

// Function to find longest common substring
void longestCommonSubstring(char *s1, char *s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int dp[len1 + 1][len2 + 1];
    int max_len = 0;
    int end_index = 0; // end index of substring in s1

    // Initialize dp array with 0
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            dp[i][j] = 0;
        }
    }

    // Build dp matrix
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1; // extend previous match
                if (dp[i][j] > max_len) {
                    max_len = dp[i][j];
                    end_index = i - 1; // update end index
                }
            } else {
                dp[i][j] = 0; // no match, reset
            }
        }
    }

    // Print the longest common substring
    if (max_len == 0) {
        printf("No common substring found\n");
    } else {
        printf("Longest common substring length = %d\n", max_len);
        printf("Longest common substring = ");
        for (int i = end_index - max_len + 1; i <= end_index; i++) {
            putchar(s1[i]);
        }
        printf("\n");
    }
}

int main() {
    char s1[] = "ABCDXYZ";
    char s2[] = "XYZABCD";
    longestCommonSubstring(s1, s2);
    return 0;
}

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

extend length of substring when characters match

if (dp[i][j] > max_len) { max_len = dp[i][j]; end_index = i - 1; }

update max length and end index of longest substring found

dp[i][j] = 0; // no match, reset

reset length when characters do not match

Output

Longest common substring length = 4

Longest common substring = ABCD

Complexity Analysis

Time: O(m*n) because we fill a 2D table comparing each character of both strings

Space: O(m*n) because we store substring lengths for all pairs of indices

vs Alternative: Naive approach checks all substrings with O(m^2*n) or worse, so DP is much faster

Edge Cases

One or both strings empty

No common substring found, output indicates zero length

DSA C

if (max_len == 0) { printf("No common substring found\n"); }

No common characters at all

No common substring found, output indicates zero length

DSA C

if (max_len == 0) { printf("No common substring found\n"); }

Strings are identical

Longest common substring is the entire string

DSA C

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

When to Use This Pattern

When asked to find the longest exact matching continuous sequence between two strings, use the longest common substring pattern with dynamic programming to efficiently track matches.

Common Mistakes

Mistake: Confusing longest common substring with longest common subsequence (which allows gaps)
Fix: Remember substring must be continuous; reset dp to zero when characters don't match

Mistake: Not updating max length and end index inside the nested loops
Fix: Update max_len and end_index immediately when a longer substring is found

Summary

Finds the longest continuous matching substring between two strings.

Use when you need the longest exact sequence shared by both strings without gaps.

The key is to build a table of substring lengths and reset when characters differ.

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"