Longest Common Substring in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Common Substring Length Calculation

What is the output of the following C code that calculates the length of the longest common substring between two strings?

DSA C

int longestCommonSubstring(char *s1, char *s2) {
    int maxLen = 0;
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int dp[len1+1][len2+1];
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            dp[i][j] = 0;
        }
    }
    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;
                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                }
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return maxLen;
}

int main() {
    char s1[] = "abcdef";
    char s2[] = "zcdemf";
    printf("%d", longestCommonSubstring(s1, s2));
    return 0;
}

A 3

B 2

C 4

D 1

💡 Hint

Check the longest continuous matching substring between the two strings.

The longest common substring between "abcdef" and "zcdemf" is "cde" which has length 3.

🧠 Conceptual

intermediate

Understanding the Difference Between Longest Common Substring and Longest Common Subsequence

Which statement correctly describes the difference between the longest common substring and the longest common subsequence of two strings?

A Longest common subsequence requires characters to be contiguous in both strings, while longest common substring does not.

B Longest common substring requires characters to be contiguous in both strings, while longest common subsequence does not.

C Both require characters to be contiguous in both strings.

D Neither requires characters to be contiguous in both strings.

💡 Hint

Think about whether the characters must be next to each other or can be spread out.

Longest common substring needs the matching characters to be next to each other in both strings. Longest common subsequence allows characters to be in order but not necessarily contiguous.

🔧 Debug

advanced

Identify the Bug in Longest Common Substring Implementation

What error will the following C code produce when run, and why?

DSA C

int longestCommonSubstring(char *s1, char *s2) {
    int maxLen = 0;
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int dp[len1][len2];
    for (int i = 0; i < len1; i++) {
        for (int j = 0; j < len2; j++) {
            dp[i][j] = 0;
        }
    }
    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;
                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                }
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return maxLen;
}

A Segmentation fault due to accessing dp out of bounds.

B Compilation error due to missing header files.

C Returns 0 always because dp is never updated.

D Runs correctly and returns the longest common substring length.

💡 Hint

Check the size of dp and the indices used to access it.

The dp array is declared with size [len1][len2], but the code accesses dp[i][j] where i and j go up to len1 and len2 inclusive, causing out-of-bounds access and segmentation fault.

🚀 Application

advanced

Longest Common Substring in DNA Sequences

Given two DNA sequences, which approach is best to find the longest common substring efficiently?

A Use recursion without memoization to explore all substring matches.

B Use a brute force approach checking all substrings of one sequence in the other.

C Use dynamic programming with a 2D array to track matching substrings.

D Use a hash set to store all substrings of the first sequence and check the second.

💡 Hint

Consider time complexity and memory usage for large sequences.

Dynamic programming with a 2D array efficiently computes the longest common substring in O(n*m) time, suitable for DNA sequences. Brute force and recursion are too slow, and hash sets are inefficient for substring matching.

🧠 Conceptual

expert

Time Complexity of Longest Common Substring Algorithm

What is the time complexity of the standard dynamic programming algorithm to find the longest common substring of two strings of lengths n and m?

A O(max(n, m))

B O(n + m)

C O(n^2 * m^2)

D O(n * m)

💡 Hint

Consider the nested loops iterating over both strings.

The algorithm uses two nested loops each running up to n and m, resulting in O(n * m) time complexity.

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"