Longest Common Substring in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Common Substring Length Calculation

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

DSA Java

public class Main {
    public static int longestCommonSubstring(String s1, String s2) {
        int maxLen = 0;
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLen = Math.max(maxLen, dp[i][j]);
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubstring("abcde", "abfde"));
    }
}

A 3

B 2

C 4

D 1

💡 Hint

Check the longest sequence of matching characters in order.

The longest common substring between "abcde" and "abfde" is "ab" which has length 2.

❓ Predict Output

intermediate

Longest Common Substring Result with Overlapping Substrings

What will be printed by this Java program that finds the longest common substring length?

DSA Java

public class Main {
    public static int longestCommonSubstring(String s1, String s2) {
        int maxLen = 0;
        int[][] dp = new int[s1.length() + 1][s2.length() + 1];
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLen = Math.max(maxLen, dp[i][j]);
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubstring("ababc", "babca"));
    }
}

A 4

B 3

C 5

D 2

💡 Hint

Look for the longest continuous matching substring.

The longest common substring is "abca" starting at index 1 in s1 and index 1 in s2, length 4.

🔧 Debug

advanced

Identify the Error in Longest Common Substring Implementation

What error will this Java code produce when run?

DSA Java

public class Main {
    public static int longestCommonSubstring(String s1, String s2) {
        int maxLen = 0;
        int[][] dp = new int[s1.length()][s2.length()];
        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    maxLen = Math.max(maxLen, dp[i][j]);
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestCommonSubstring("abc", "abc"));
    }
}

A No error, output is 3

B NullPointerException

C Compilation error

D ArrayIndexOutOfBoundsException

💡 Hint

Check array size and loop indices carefully.

The dp array is sized s1.length() x s2.length(), but loops start at 1 and access dp[i][j], causing index out of bounds.

🧠 Conceptual

advanced

Longest Common Substring vs Longest Common Subsequence

Which statement correctly describes the difference between Longest Common Substring and Longest Common Subsequence?

A Both require characters to be contiguous but differ in case sensitivity.

B Longest Common Subsequence requires characters to be contiguous; Longest Common Substring does not require contiguity.

C Longest Common Substring requires characters to be contiguous; Longest Common Subsequence does not require contiguity.

D Both are the same and always produce the same result.

💡 Hint

Think about whether characters must be next to each other.

Longest Common Substring needs characters to be next to each other in both strings. Longest Common Subsequence allows skipping characters.

🚀 Application

expert

Longest Common Substring Length for Large Inputs

Given two strings each of length 100000 containing only 'a' characters, what is the length of their longest common substring?

A 100000

B 99999

C 1

D 0

💡 Hint

All characters match and are contiguous.

Since both strings are identical and contain only 'a's, the entire string is the longest common substring.

Practice

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

easy

A. The total number of common characters between the two strings

B. The longest sequence of characters that appear in any order in both strings

C. The longest sequence of characters that appear only in the first string

D. The longest sequence of characters that appear consecutively in both strings

Solution

1. Step 1: Understand the problem definition

   The Longest Common Substring problem looks for the longest continuous sequence of characters that appear exactly the same and consecutively in both strings.

2. Step 2: Compare options with the definition

   The longest sequence of characters that appear consecutively in both strings correctly describes this as a consecutive sequence. Options B and C describe subsequences or counts, not substrings. The longest sequence of characters that appear only in the first string is unrelated.

3. Final Answer:

   The longest sequence of characters that appear consecutively in both strings -> Option D

4. Quick Check:

   Longest Common Substring = Consecutive matching sequence [OK]

Hint: Longest Common Substring means continuous matching characters [OK]

Common Mistakes:

• Confusing substring with subsequence
• Thinking order does not matter
• Counting total common characters instead

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

easy

A. int[][] dp = new int[m][n];

B. int[][] dp = new int[m+1][n+1];

C. int dp[][] = new int[m-1][n-1];

D. int dp[][] = new int[m+1];

Solution

1. Step 1: Understand array size for DP table

   For Longest Common Substring, we use a DP table of size (m+1) x (n+1) to handle empty prefixes of both strings.

2. Step 2: Check each option's correctness

   int[][] dp = new int[m+1][n+1]; correctly creates a 2D array with dimensions m+1 and n+1. int[][] dp = new int[m][n]; misses the +1, int dp[][] = new int[m-1][n-1]; uses m-1 and n-1 which is invalid, and int dp[][] = new int[m+1]; creates a 1D array.

3. Final Answer:

   int[][] dp = new int[m+1][n+1]; -> Option B

4. Quick Check:

   DP array size = (m+1) x (n+1) [OK]

Hint: DP table size is string lengths plus one for empty prefix [OK]

Common Mistakes:

• Using wrong array dimensions without +1
• Declaring 1D array instead of 2D
• Using negative or zero sizes

3. What is the output of the following Java code snippet?

String s1 = "abcdxyz";
String s2 = "xyzabcd";
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.charAt(i-1) == s2.charAt(j-1)) {
      dp[i][j] = dp[i-1][j-1] + 1;
      maxLen = Math.max(maxLen, dp[i][j]);
    } else {
      dp[i][j] = 0;
    }
  }
}
System.out.println(maxLen);

medium

A. 4

B. 3

C. 1

D. 0

Solution

1. Step 1: Understand the strings and DP logic

   s1 = "abcdxyz", s2 = "xyzabcd". The code finds the longest common substring length using DP.

2. Step 2: Trace the longest common substring

   The longest common substring is "abcd" which appears consecutively in both strings (s1[0-3], s2[3-6]). Its length is 4. "xyz" appears consecutively with length 3.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Longest common substring length = 4 [OK]

Hint: Check longest consecutive matching substring length [OK]

Common Mistakes:

• Confusing substring with subsequence
• Missing the diagonal match for 'abcd'
• Ignoring DP reset to zero on mismatch

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

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.charAt(i) == s2.charAt(j)) {
      dp[i][j] = dp[i-1][j-1] + 1;
      maxLen = Math.max(maxLen, dp[i][j]);
    } else {
      dp[i][j] = 0;
    }
  }
}
System.out.println(maxLen);

medium

A. maxLen is not updated correctly

B. DP array size is too small

C. Index out of bounds due to incorrect charAt indices

D. The else block should not reset dp[i][j] to zero

Solution

1. Step 1: Check charAt indices usage

   In Java, string indices start at 0, but the loop runs i and j from 1 to length. Using s1.charAt(i) and s2.charAt(j) causes index out of bounds when i or j equals length.

2. Step 2: Correct index usage

   Indices should be i-1 and j-1 to access characters correctly inside the loop.

3. Final Answer:

   Index out of bounds due to incorrect charAt indices -> Option C

4. Quick Check:

   charAt indices must be i-1, j-1 [OK]

Hint: Use i-1 and j-1 for string charAt in DP loops [OK]

Common Mistakes:

• Using i and j directly as string indices
• Not adjusting for zero-based indexing
• Ignoring array bounds errors

5. Given two strings s1 = "banana" and s2 = "ananas", which of the following Java methods correctly returns the longest common substring length?

hard

A. Use nested loops with DP, update dp[i][j] = dp[i-1][j-1] + 1 if chars match, else 0, track maxLen

B. Use nested loops, increment dp[i][j] by 1 on mismatch, else reset to 0

C. Use nested loops, update dp[i][j] = dp[i][j-1] + 1 if chars match

D. Use nested loops, count total matching characters without resetting dp

Solution

1. Step 1: Recall DP approach for Longest Common Substring

   We use a 2D DP array where dp[i][j] stores length of longest common substring ending at s1[i-1] and s2[j-1]. If characters match, dp[i][j] = dp[i-1][j-1] + 1; else 0.

2. Step 2: Evaluate each option

   Use nested loops with DP, update dp[i][j] = dp[i-1][j-1] + 1 if chars match, else 0, track maxLen correctly describes this approach. Options A, C, and D describe incorrect logic that does not reset on mismatch or use wrong indices.

3. Final Answer:

   Use nested loops with DP, update dp[i][j] = dp[i-1][j-1] + 1 if chars match, else 0, track maxLen -> Option A

4. Quick Check:

   DP update with reset on mismatch = correct method [OK]

Hint: Reset DP cell to zero on mismatch, add 1 on match [OK]

Common Mistakes:

• Not resetting DP cell to zero on mismatch
• Using wrong DP update formula
• Counting subsequence instead of substring