Longest Common Substring in DSA Java - Build from Scratch

Longest Common Substring

📖 Scenario: You are working on a text comparison tool that helps find the longest common substring between two given words. This is useful in spell checkers, plagiarism detectors, and DNA sequence analysis.

🎯 Goal: Build a Java program that finds the longest common substring between two given strings using dynamic programming.

📋 What You'll Learn

Create two string variables with exact values

Create a 2D integer array to store substring lengths

Implement nested loops to fill the array and find the longest common substring length and position

Print the longest common substring found

💡 Why This Matters

🌍 Real World

Finding longest common substrings helps in text comparison tools like spell checkers, plagiarism detection, and DNA sequence analysis.

💼 Career

Understanding dynamic programming and string manipulation is essential for software development roles involving algorithms, data processing, and bioinformatics.

1

Create the input strings

Create two string variables called str1 and str2 with the exact values "ABABC" and "BABCA" respectively.

DSA Java

# Create two strings str1 and str2 with values "ABABC" and "BABCA"
// Your code here

Hint

Use String str1 = "ABABC"; and String str2 = "BABCA"; to create the strings.

2

Create the 2D array and helper variables

Create a 2D integer array called dp with size str1.length() + 1 by str2.length() + 1. Also create two integer variables called maxLength and endIndex initialized to 0.

DSA Java

public class LongestCommonSubstring {
    public static void main(String[] args) {
        String str1 = "ABABC";
        String str2 = "BABCA";
        // Create dp array and helper variables maxLength and endIndex
        // Your code here
    }
}

Hint

Use int[][] dp = new int[str1.length() + 1][str2.length() + 1]; to create the array.

Initialize maxLength and endIndex to 0.

3

Fill the dp array and find the longest substring

Use nested for loops with variables i from 1 to str1.length() and j from 1 to str2.length(). Inside, check if str1.charAt(i - 1) == str2.charAt(j - 1). If true, set dp[i][j] = dp[i - 1][j - 1] + 1. If dp[i][j] > maxLength, update maxLength = dp[i][j] and endIndex = i.

DSA Java

public class LongestCommonSubstring {
    public static void main(String[] args) {
        String str1 = "ABABC";
        String str2 = "BABCA";
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        int maxLength = 0;
        int endIndex = 0;
        // Use nested for loops to fill dp and find maxLength and endIndex
        // Your code here
    }
}

Hint

Use two nested loops from 1 to the length of each string.

Compare characters at i-1 and j-1.

Update dp[i][j] and track maxLength and endIndex.

4

Print the longest common substring

Use System.out.println to print the substring of str1 from endIndex - maxLength to endIndex. Use str1.substring(endIndex - maxLength, endIndex).

DSA Java

public class LongestCommonSubstring {
    public static void main(String[] args) {
        String str1 = "ABABC";
        String str2 = "BABCA";
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        int maxLength = 0;
        int endIndex = 0;
        for (int i = 1; i  maxLength) {
                        maxLength = dp[i][j];
                        endIndex = i;
                    }
                }
            }
        }
        // Print the longest common substring
        // Your code here
    }
}

Hint

Use System.out.println(str1.substring(endIndex - maxLength, endIndex)); to print the result.

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