Longest Common Substring in DSA Java - Time & Space Complexity

Time Complexity: Longest Common Substring

O(n * m)

Understanding Time Complexity

We want to understand how the time needed to find the longest common substring grows as the input strings get longer.

How does the work increase when the strings become bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public 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;
}
    

This code finds the length of the longest substring that appears in both input strings by building a table of matching character lengths.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops comparing characters of both strings.
• How many times: Outer loop runs for length of first string (n), inner loop runs for length of second string (m), so total n * m times.

How Execution Grows With Input

As the strings get longer, the number of comparisons grows by multiplying their lengths.

Input Size (n = m)	Approx. Operations
10	100
100	10,000
1000	1,000,000

Pattern observation: Doubling the length roughly quadruples the work, showing a square growth pattern.

Final Time Complexity

Time Complexity: O(n * m)

This means the time needed grows proportionally to the product of the lengths of the two strings.

Common Mistake

[X] Wrong: "The algorithm runs in linear time because it just loops through the strings once."

[OK] Correct: The algorithm uses two nested loops, so it compares each character of the first string with each character of the second, making the work multiply, not just add.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming solutions scale and why nested loops matter, a skill useful in many coding challenges.

Self-Check

"What if we used a suffix tree instead of dynamic programming? How would the time complexity change?"

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