Longest Common Substring in DSA Java

Mental Model

Find the longest sequence of characters that appears exactly the same and continuously in both strings.

Analogy: Imagine two friends reading two different books and trying to find the longest exact phrase that appears in both books without breaks.

String1: a b c d e f g
String2: x y c d e z
Longest common substring: c d e

Dry Run Walkthrough

Input: String1: "abcde", String2: "abfde"

Goal: Find the longest continuous substring that appears in both strings.

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

dp matrix initialized with zeros for dimensions 6x6 (lengths +1)

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

Step 2: Compare characters at String1[1]='a' and String2[1]='a', they match

dp[1][1] = 1
Longest length updated to 1

Why: Matching characters start a common substring of length 1

Step 3: Compare String1[2]='b' and String2[2]='b', they match

dp[2][2] = dp[1][1] + 1 = 2
Longest length updated to 2

Why: Extending previous substring by one character

Step 4: Compare String1[3]='c' and String2[3]='f', no match

dp[3][3] = 0
Longest length remains 2

Why: Mismatch breaks the substring continuity

Step 5: Compare String1[4]='d' and String2[4]='d', they match

dp[4][4] = 1
Longest length remains 2

Why: New substring starts here but length 1 is less than current longest

Step 6: Compare String1[5]='e' and String2[5]='e', they match

dp[5][5] = dp[4][4] + 1 = 2
Longest length remains 2

Why: Extending substring ending at previous characters

Result:

Longest common substring length = 2, substring = "ab"

Annotated Code

DSA Java

public class LongestCommonSubstring {
    public static String longestCommonSubstring(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int[][] dp = new int[m + 1][n + 1];
        int maxLength = 0;
        int endIndex = 0; // end index of substring in s1

        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; // extend previous substring
                    if (dp[i][j] > maxLength) {
                        maxLength = dp[i][j];
                        endIndex = i; // update end index
                    }
                } else {
                    dp[i][j] = 0; // reset on mismatch
                }
            }
        }
        return maxLength == 0 ? "" : s1.substring(endIndex - maxLength, endIndex);
    }

    public static void main(String[] args) {
        String s1 = "abcde";
        String s2 = "abfde";
        String result = longestCommonSubstring(s1, s2);
        System.out.println("Longest Common Substring: " + result);
    }
}

if (s1.charAt(i - 1) == s2.charAt(j - 1)) {

Check if characters match to extend substring

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

Extend length of common substring by 1 from previous diagonal

if (dp[i][j] > maxLength) {

Update max length and end index if longer substring found

dp[i][j] = 0;

Reset length to zero on character mismatch

Output

Longest Common Substring: ab

Complexity Analysis

Time: O(m*n) because we fill a 2D table comparing each character pair once

Space: O(m*n) for the dp table storing substring lengths for all pairs

vs Alternative: Naive approach checks all substrings leading to O(m^2*n^2) time, so DP is much faster

Edge Cases

One or both strings empty

Returns empty string as no common substring exists

DSA Java

int m = s1.length(); int n = s2.length();

No common substring

Returns empty string since maxLength remains zero

DSA Java

if (dp[i][j] > maxLength) {

Strings are identical

Returns the entire string as longest common substring

DSA Java

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

When to Use This Pattern

When asked to find the longest continuous matching part 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 requires continuous characters; reset dp to zero on mismatch

Mistake: Not updating the end index when a longer substring is found
Fix: Update endIndex whenever maxLength is updated to track substring position

Summary

Finds the longest continuous matching substring between two strings.

Use when you need the longest exact sequence of characters shared by both strings without breaks.

Track substring lengths in a table and reset on mismatches to find the longest continuous match.

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