Longest Common Substring in DSA Java - Deep Dive

Overview - Longest Common Substring

What is it?

The Longest Common Substring problem finds the longest sequence of characters that appears in the same order and contiguously in two given strings. Unlike subsequences, substrings must be continuous parts of the strings. This problem helps identify the biggest exact matching part between two texts.

Why it matters

Finding the longest common substring is important in areas like DNA analysis, plagiarism detection, and file comparison. Without this concept, computers would struggle to quickly find exact matching parts between texts, making many applications slow or inaccurate.

Where it fits

Before learning this, you should understand basic strings and arrays. After mastering this, you can explore related problems like Longest Common Subsequence and advanced string matching algorithms.

Mental Model

Core Idea

The longest common substring is the longest continuous sequence of characters shared by two strings.

Think of it like...

Imagine two ribbons with colored beads. The longest common substring is like finding the longest stretch of beads with the exact same colors in the same order on both ribbons without skipping any bead.

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

Longest Common Substring: B C D

Visualization:

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

The vertical bars show the matching continuous substring.

Build-Up - 7 Steps

1

Foundation

Understanding substrings and continuity

Concept: Learn what substrings are and how continuity matters.

A substring is a continuous part of a string. For example, in "hello", "ell" is a substring but "hlo" is not because the letters are not continuous. This continuity is key to the problem.

Result

You can identify substrings by selecting continuous characters from a string.

Understanding continuity helps distinguish substrings from subsequences, which is crucial for this problem.

2

Foundation

Comparing two strings character by character

Concept: Learn how to compare two strings to find matching characters.

To find common parts, compare each character of the first string with each character of the second string. Mark where characters match to find potential substrings.

Result

You can spot matching characters and their positions in both strings.

Knowing how to compare characters sets the stage for building solutions that track matching substrings.

3

Intermediate

Dynamic programming table setup

🤔Before reading on: do you think we need to store all substring matches or just the longest one? Commit to your answer.

Concept: Use a table to store lengths of matching substrings ending at each pair of positions.

Create a 2D table where rows represent characters of the first string and columns represent characters of the second string. Each cell stores the length of the longest common substring ending at those positions. If characters match, add 1 to the diagonal cell's value; else, zero.

Result

A filled table showing lengths of matching substrings at every position pair.

Using a table to store intermediate results avoids repeated work and efficiently finds the longest substring.

4

Intermediate

Tracking maximum substring length and position

🤔Before reading on: do you think the longest substring always ends at the last characters of the strings? Commit to your answer.

Concept: Keep track of the maximum length found and where it ends in the first string.

While filling the table, update a variable whenever a longer substring length is found. Store the ending index in the first string to later extract the substring.

Result

You know the length and position of the longest common substring after processing.

Tracking max length and position during computation lets you retrieve the substring without extra passes.

5

Intermediate

Extracting the longest common substring

Concept: Use the stored position and length to get the substring from the first string.

Once the table is complete and max length and end position are known, extract the substring from the first string starting at (end position - max length + 1) to end position.

Result

The actual longest common substring string.

Knowing how to extract the substring completes the problem solution and connects the table data to the final answer.

6

Advanced

Optimizing space with rolling arrays

🤔Before reading on: do you think we need to keep the entire 2D table in memory? Commit to your answer.

Concept: Reduce memory use by storing only the current and previous row of the table.

Since each cell depends only on the diagonal previous cell, keep two 1D arrays representing the current and previous rows. Update them as you move through the strings.

Result

A space-efficient solution using O(min(m,n)) memory instead of O(m*n).

Understanding dependencies in the table allows memory optimization without losing correctness.

7

Expert

Handling multiple longest substrings and ties

🤔Before reading on: do you think there can be more than one longest common substring? Commit to your answer.

Concept: Recognize that multiple substrings of the same maximum length can exist and how to find them.

Modify the algorithm to store all ending positions where the max length occurs. Extract all substrings from these positions. This helps in applications needing all matches, not just one.

Result

A list of all longest common substrings when ties occur.

Knowing how to handle ties prepares you for real-world cases where multiple answers matter.

Under the Hood

The algorithm builds a 2D table where each cell represents the length of the longest common substring ending at the corresponding characters of the two strings. It uses previous computations (diagonal neighbors) to extend substrings. This dynamic programming approach avoids redundant checks by storing intermediate results.

Why designed this way?

This method was designed to efficiently solve the problem in polynomial time, avoiding exponential brute force checks of all substrings. Alternatives like suffix trees exist but are more complex to implement. The table approach balances clarity and performance.

  +-----------------------------+
  |   DP Table (Lengths)        |
  +-----------------------------+
  |   | X | Y | B | C | D | Z |  
  +---+---+---+---+---+---+---+
  | A | 0 | 0 | 0 | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+
  | B | 0 | 0 | 1 | 0 | 0 | 0 |
  +---+---+---+---+---+---+---+
  | C | 0 | 0 | 0 | 2 | 0 | 0 |
  +---+---+---+---+---+---+---+
  | D | 0 | 0 | 0 | 0 | 3 | 0 |
  +---+---+---+---+---+---+---+

Each cell shows length of substring ending at those chars.

Myth Busters - 4 Common Misconceptions

Quick: Does the longest common substring always appear at the start of one of the strings? Commit to yes or no.

Common Belief: The longest common substring must start at the beginning of one of the strings.

Reality: The longest common substring can appear anywhere inside both strings, not necessarily at the start.

Why it matters: Assuming it starts at the beginning can cause incorrect solutions that miss valid substrings.

Quick: Is the longest common substring the same as the longest common subsequence? Commit to yes or no.

Common Belief: Longest common substring and longest common subsequence are the same problem.

Reality: They differ: substrings require continuity, subsequences do not. This changes the approach and results.

Why it matters: Confusing these leads to wrong algorithms and wrong answers.

Quick: Can the longest common substring be empty if the strings share some characters? Commit to yes or no.

Common Belief: If two strings share characters, the longest common substring is never empty.

Reality: If shared characters are not contiguous, the longest common substring can be empty (length zero).

Why it matters: Assuming non-empty substring causes errors in edge cases with no continuous matches.

Quick: Does storing only the maximum length suffice to find the substring? Commit to yes or no.

Common Belief: Knowing the maximum length alone is enough to get the substring.

Reality: You also need the position where this maximum length ends to extract the substring.

Why it matters: Without position, you cannot retrieve the actual substring, only its length.

Expert Zone

1

The DP table's diagonal dependency means only two rows need storage, enabling space optimization.

2

Suffix trees or suffix arrays can solve this problem faster for multiple queries but are complex to implement.

3

Handling multiple longest substrings requires tracking all max-length positions, not just one.

When NOT to use

Avoid this DP approach when working with very large strings and multiple queries; use suffix trees or suffix arrays instead for better performance.

Production Patterns

Used in plagiarism detection tools to find exact copied parts, in bioinformatics to find matching DNA sequences, and in file comparison utilities to highlight common parts.

Connections

Longest Common Subsequence

Related problem with similar goals but different constraints (continuity vs. order only).

Understanding the difference clarifies when to use substring vs subsequence algorithms.

Suffix Trees

Advanced data structure that can solve longest common substring efficiently for multiple queries.

Knowing suffix trees helps optimize solutions beyond DP for large-scale problems.

Genetics Sequence Alignment

Longest common substring algorithms help find exact matching DNA segments.

Recognizing this connection shows how computer science algorithms apply to biology.

Common Pitfalls

#1 Confusing substring with subsequence and allowing non-continuous matches.

Wrong approach:

if (string1.charAt(i) == string2.charAt(j)) {
length = previous_length + 1; // without checking continuity
}

Correct approach:

if (string1.charAt(i) == string2.charAt(j)) {
length = dp[i-1][j-1] + 1; // only extend if previous chars matched
} else {
length = 0;
}

Root cause:

Not resetting length to zero when characters don't match breaks substring continuity.

#2 Only storing maximum length without tracking position to extract substring.

Wrong approach:

int maxLength = 0;
for all dp[i][j]:
if (dp[i][j] > maxLength) maxLength = dp[i][j];
// no position stored

Correct approach:

int maxLength = 0, endIndex = 0;
for all dp[i][j]:
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
endIndex = i;
}

Root cause:

Forgetting that length alone doesn't tell where substring ends.

#3 Using full 2D table without optimization for large strings causing memory issues.

Wrong approach:

int[][] dp = new int[m][n]; // large memory for big strings

Correct approach:

int[] prev = new int[n];
int[] curr = new int[n];
// update curr using prev and swap references

Root cause:

Not recognizing dependency only on previous row wastes memory.

Key Takeaways

The longest common substring is the longest continuous matching part between two strings, different from subsequences.

Dynamic programming efficiently solves this by building a table of substring lengths ending at each character pair.

Tracking both maximum length and position is essential to extract the actual substring.

Space can be optimized by storing only two rows of the DP table at a time.

Advanced data structures like suffix trees offer faster solutions for large-scale or multiple queries.

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