Longest Common Substring in DSA Java - Execution Trace

Concept Flow - Longest Common Substring

Start with two strings

↓

Create 2D array dp

↓

For each char in string1

↓

For each char in string2

↓

If chars match

↓

dp[i

↓

Update max length and position

↓

Else dp[i

↓

After loops, extract substring from max position

↓

Return longest common substring

↓

End

We compare characters of two strings using a 2D table to find the longest matching substring by building lengths step-by-step.

Execution Sample

DSA Java

String s1 = "abcde";
String s2 = "abfde";
int[][] dp = new int[s1.length()+1][s2.length()+1];
int maxLen = 0, endPos = 0;
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;
      if (dp[i][j] > maxLen) {
        maxLen = dp[i][j];
        endPos = i;
      }
    } else {
      dp[i][j] = 0;
    }
  }
}

This code builds a table to find the longest substring common to both strings by checking character matches.

Execution Table

Step	Operation	Indices (i,j)	Chars Compared	dp[i][j] Value	Max Length	Max End Position	Visual dp State (partial)
1	Initialize dp array	-	-	-	0	0	All zeros
2	Compare chars	(1,1)	'a' vs 'a'	1	1	1	dp[1][1]=1
3	Compare chars	(1,2)	'a' vs 'b'	0	1	1	dp[1][2]=0
4	Compare chars	(1,3)	'a' vs 'f'	0	1	1	dp[1][3]=0
5	Compare chars	(1,4)	'a' vs 'd'	0	1	1	dp[1][4]=0
6	Compare chars	(1,5)	'a' vs 'e'	0	1	1	dp[1][5]=0
7	Compare chars	(2,1)	'b' vs 'a'	0	1	1	dp[2][1]=0
8	Compare chars	(2,2)	'b' vs 'b'	2	2	2	dp[2][2]=2
9	Compare chars	(2,3)	'b' vs 'f'	0	2	2	dp[2][3]=0
10	Compare chars	(2,4)	'b' vs 'd'	0	2	2	dp[2][4]=0
11	Compare chars	(2,5)	'b' vs 'e'	0	2	2	dp[2][5]=0
12	Compare chars	(3,1)	'c' vs 'a'	0	2	2	dp[3][1]=0
13	Compare chars	(3,2)	'c' vs 'b'	0	2	2	dp[3][2]=0
14	Compare chars	(3,3)	'c' vs 'f'	0	2	2	dp[3][3]=0
15	Compare chars	(3,4)	'c' vs 'd'	0	2	2	dp[3][4]=0
16	Compare chars	(3,5)	'c' vs 'e'	0	2	2	dp[3][5]=0
17	Compare chars	(4,1)	'd' vs 'a'	0	2	2	dp[4][1]=0
18	Compare chars	(4,2)	'd' vs 'b'	0	2	2	dp[4][2]=0
19	Compare chars	(4,3)	'd' vs 'f'	0	2	2	dp[4][3]=0
20	Compare chars	(4,4)	'd' vs 'd'	1	2	2	dp[4][4]=1
21	Compare chars	(4,5)	'd' vs 'e'	0	2	2	dp[4][5]=0
22	Compare chars	(5,1)	'e' vs 'a'	0	2	2	dp[5][1]=0
23	Compare chars	(5,2)	'e' vs 'b'	0	2	2	dp[5][2]=0
24	Compare chars	(5,3)	'e' vs 'f'	0	2	2	dp[5][3]=0
25	Compare chars	(5,4)	'e' vs 'd'	0	2	2	dp[5][4]=0
26	Compare chars	(5,5)	'e' vs 'e'	1	2	2	dp[5][5]=1
27	End loops	-	-	-	2	2	Final maxLen=2, endPos=2
28	Extract substring	-	-	-	2	2	Longest substring: 'ab'
29	Return result	-	-	-	2	2	Output: 'ab'

💡 All characters compared; max length found at dp[2][2] with length 2

Variable Tracker

Variable	Start	After Step 2	After Step 8	After Step 20	After Step 26	Final
maxLen	0	1	2	2	2	2
endPos	0	1	2	2	2	2
dp[1][1]	0	1	1	1	1	1
dp[2][2]	0	0	2	2	2	2
dp[4][4]	0	0	0	1	1	1
dp[5][5]	0	0	0	0	1	1

Key Moments - 3 Insights

Why do we reset dp[i][j] to 0 when characters don't match?

Because the longest common substring must be continuous. When chars differ, the substring breaks, so dp[i][j] is 0 (see steps 3,4,5).

Why do we start indices i and j from 1 in dp array?

We use dp array with extra row and column (size+1) to avoid index errors and to handle empty prefixes easily (see initialization at step 1).

How do we find the longest substring after filling dp?

We track maxLen and endPos during filling (steps 2,8,20,26). After loops, substring is s1 from endPos-maxLen to endPos (step 28).

Visual Quiz - 3 Questions

Look at the execution_table at step 8, what is the dp[2][2] value and what does it represent?

A dp[2][2] = 1, length of substring 'a'

B dp[2][2] = 0, no match

C dp[2][2] = 2, length of substring 'ab'

D dp[2][2] = 3, length of substring 'abc'

💡 Hint

Check step 8 row in execution_table for dp[i][j] and max length

At which step does the maxLen first update to 2?

A Step 8

B Step 20

C Step 2

D Step 26

💡 Hint

Look at maxLen column in execution_table rows

If the characters at (4,4) were matching longer, how would dp[4][4] value change?

A It would be 1

B It would be dp[3][3] + 1

C It would be 0

D It would be maxLen + 2

💡 Hint

Recall dp[i][j] = dp[i-1][j-1] + 1 when chars match

Concept Snapshot

Longest Common Substring (LCS) finds the longest continuous matching part of two strings.
Use a 2D dp array where dp[i][j] stores length of matching substring ending at s1[i-1] and s2[j-1].
If chars match, dp[i][j] = dp[i-1][j-1] + 1; else 0.
Track max length and position during filling.
Extract substring from s1 using max length and end position.
Time complexity: O(n*m), space: O(n*m).

Full Transcript

Longest Common Substring compares two strings character by character using a 2D table called dp. Each cell dp[i][j] holds the length of the longest substring ending at those positions if characters match. If they don't match, dp[i][j] is zero because the substring must be continuous. We start indices from 1 to handle empty prefixes easily. While filling dp, we keep track of the maximum length found and where it ends. After filling, we extract the substring from the first string using these values. This method ensures we find the longest continuous matching substring efficiently.

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