DP 27. Longest Common Substring | DP on Strings

1. Why Do We Need This? (Problem Statement & Status Quo)

In the previous video, we explored the Longest Common Subsequence (LCS) problem. A subsequence allows us to pick characters from a string while maintaining their relative order, but they do not need to be consecutive.

Now, we examine a stricter variation: the Longest Common Substring.

• Subsequence (Previous): Characters can have gaps between them (e.g., in abcde, ace is a valid subsequence).
• Substring (Current): Characters must be strictly contiguous/consecutive. There can be zero gaps or skipped characters.

The Core Contrast

Given two strings, S1 and S2, we want to find the length of the longest contiguous segment that appears in both strings.

String 1: A B C D
String 2: A B Z D

Longest Common Subsequence: A B D (Length: 3, gaps allowed)
Longest Common Substring:  A B   (Length: 2, strictly consecutive)

2. Core Mental Model & The Failure of the LCS Formula

Why the Naive LCS Approach Fails

In Longest Common Subsequence, our recurrence relation handled non-matching characters by omitting one character from either string:

// LCS Recurrence (For Subsequence)
if (S1[i] == S2[j]) {
    dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}

The Flaw for Substrings: When characters don't match, LCS takes max(dp[i-1][j], dp[i][j-1]), which essentially omits a character and carries forward previous matches. Because substrings must be consecutive, carrying forward a match across a mismatch violates the contiguity rule. We cannot simply "skip" a character and stitch non-adjacent pieces together.

3. Naive vs. Better Approach

4. Step-by-Step Evolution: The Tabulation Strategy

Because we need strict consecutiveness, any mismatch breaks the common substring chain instantly. Therefore, our DP table stores the length of the longest common substring ending at index i in string 1 and index j in string 2.

Recurrence Mechanics

1. If characters match (S1[i] == S2[j]):
   JAVA

   Copy

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

2. If characters do not match (S1[i] != S2[j]):
   JAVA

   Copy

   dp[i][j] = 0; // Chain is broken! No carrying forward.
   

5. Complete Flow Walkthrough (Tabulation Table)

Let's trace S1 = "abcd" and S2 = "abzd" using 1-based indexing in our DP table.

       ""    a    b    z    d
  "" [  0,   0,   0,   0,   0 ]
   a [  0,   1,   0,   0,   0 ]
   b [  0,   0,   2,   0,   0 ]
   c [  0,   0,   0,   0,   0 ]
   d [  0,   0,   0,   0,   1 ]

Walkthrough of Cell Computations:

• S1[1] ('a') & S2[1] ('a'): Match! 1 + dp[0][0] (0) = 1.
• S1[2] ('b') & S2[2] ('b'): Match! 1 + dp[1][1] (1) = 2.
• S1[4] ('d') & S2[4] ('d'): Match! 1 + dp[3][3] (0) = 1 (since c and z did not match, dp[3][3] was 0).

Crucial Insight: The final answer is not simply the bottom-right cell (dp[N][M]). The longest common substring could have occurred anywhere in the middle of the strings. Thus, we must track the maximum value present across the entire DP matrix.

6. Code Evolution: From Tabulation to Space Optimization

Tabulation Implementation (2D DP)

Here is the complete tabular solution incorporating the zero-reset on mismatch and tracking the global maximum:

public class LongestCommonSubstring {
    public static int longestCommonSubstring(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        
        int[][] dp = new int[n + 1][m + 1];
        int ans = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                    ans = Math.max(ans, dp[i][j]);
                } else {
                    dp[i][j] = 0; // Reset on mismatch
                }
            }
        }
        
        return ans;
    }
}

Space-Optimized Implementation (1D Array)

Notice that dp[i][j] only depends on the previous row (dp[i-1][j-1]). Just like in LCS, we can optimize our space complexity from $O(N \times M)$ down to $O(M)$ by using two rows (or a single rolling array, though care must be taken with order, or working backwards).

public class LongestCommonSubstringOptimized {
    public static int longestCommonSubstring(String s1, String s2) {
        int n = s1.length();
        int m = s2.length();
        
        int[] prev = new int[m + 1];
        int ans = 0;
        
        for (int i = 1; i <= n; i++) {
            int[] curr = new int[m + 1];
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    curr[j] = 1 + prev[j - 1];
                    ans = Math.max(ans, curr[j]);
                } else {
                    curr[j] = 0; // Reset chain on mismatch
                }
            }
            prev = curr;
        }
        
        return ans;
    }
}

7. Complexity Analysis

• Time Complexity: $O(N \times M)$ where $N$ and $M$ are the lengths of strings s1 and s2. We iterate through every cell of the $N \times M$ grid exactly once.
• Space Complexity:
  • $O(N \times M)$ for the standard 2D Tabulation approach.
  • $O(M)$ for the space-optimized approach using single/double rolling arrays.

Summary and Key Takeaways

• Substring vs. Subsequence: Substrings require strict consecutiveness, whereas subsequences allow gaps.
• Mismatch Handling: Unlike LCS (which carries forward the maximum of top or left cells on mismatch), Longest Common Substring resets the cell value to 0 to break discontinuous chains.
• State Definition: dp[i][j] represents the length of the longest common substring ending exactly at s1[i-1] and s2[j-1].
• Finding the Answer: The result is not found at dp[n][m]; instead, it is the maximum value recorded anywhere in the DP table.
• Space Optimization: Because each state only depends on the diagonally previous cell (dp[i-1][j-1]), space complexity can be optimized from $O(N \times M)$ to $O(M)$.