14.30 Longest Common Substring

14.30.1 Problem Metadata

14.30.2 Description

Given two strings s1 and s2, return the length of their longest common substring (contiguous sequence).

14.30.3 Examples

Input: s1 = "abcdxyz", s2 = "xyzabcd"
Output: 4  // "abcd"

14.30.4 Constraints

  • 1 <= len(s1), len(s2) <= 10^3
  • Strings contain lowercase letters

14.30.5 Solution - 2D DP Table

14.30.5.1 Walkthrough

Let dp[i][j] represent the length of the longest common substring ending at s1[i] and s2[j]. Initialize first row/column by comparing individual characters. For each match extend from dp[i-1][j-1] + 1; otherwise reset to zero. Track the maximum length seen.

14.30.5.2 Analysis

  • Time Complexity: O(n * m)
  • Space Complexity: O(n * m)

14.30.5.3 Implementation Steps

  1. Create dp[len1][len2], initialize first row/column.
  2. For each i > 0 and j > 0, if s1[i] == s2[j] set dp[i][j] = dp[i-1][j-1] + 1, else 0.
  3. Maintain maxLen.
  4. Return maxLen.

14.30.5.4 Code - Java

public int longestCommonSubstring(String s1, String s2) {
    int n = s1.length();
    int m = s2.length();
    int[][] dp = new int[n][m];
    int max = 0;

    for (int i = 0; i < n; i++) {
        dp[i][0] = (s1.charAt(i) == s2.charAt(0)) ? 1 : 0;
        max = Math.max(max, dp[i][0]);
    }
    for (int j = 0; j < m; j++) {
        dp[0][j] = (s1.charAt(0) == s2.charAt(j)) ? 1 : 0;
        max = Math.max(max, dp[0][j]);
    }
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (s1.charAt(i) == s2.charAt(j)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                max = Math.max(max, dp[i][j]);
            } else {
                dp[i][j] = 0;
            }
        }
    }
    return max;
}