Longest Common Substring

Problem Statement

Given two strings, find the length of the longest common substring (contiguous sequence of characters that appears in both strings).

Example:

• Input: s1 = "ABCDGH", s2 = "ACDGHR"
• Output: 4 (The longest common substring is "CDGH")

Noob-Friendly Explanation

Imagine two kids each have a long sentence written on paper. They want to find the longest chunk of text that appears in BOTH sentences, letter by letter, in the same order, with no gaps. It's like finding where the two sentences overlap the most. Note: this is different from subsequence — here the characters must be next to each other (contiguous).

Approach 1: Brute Force

Intuition

Generate all possible substrings of the first string and check if each one exists in the second string. Track the longest match.

Algorithm

1. For each starting position in s1, generate all substrings.
2. For each substring, check if it exists in s2.
3. Track the longest matching substring.

class Solution {
    public static int longestCommonSubstringBrute(String s1, String s2) {
        int maxLen = 0;

        for (int i = 0; i < s1.length(); i++) {
            for (int j = i + 1; j <= s1.length(); j++) {
                String substring = s1.substring(i, j);
                if (s2.contains(substring)) {
                    maxLen = Math.max(maxLen, substring.length());
                }
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        String s1 = "ABCDGH";
        String s2 = "ACDGHR";
        System.out.println(longestCommonSubstringBrute(s1, s2)); // Output: 4
    }
}

Complexity Analysis

• Time Complexity: O(m * n * min(m,n)) - generating substrings of s1 takes O(m^2), checking each in s2 takes O(n)
• Space Complexity: O(min(m,n)) - for the substring storage

Approach 2: Optimal

Intuition

Use a 2D DP table where dp[i][j] represents the length of the longest common substring ending at s1[i-1] and s2[j-1]. If characters match, extend the previous diagonal value. If they don't, reset to 0.

Algorithm

1. Create a dp table of size (m+1) x (n+1), initialized to 0.
2. For each pair (i, j): if s1[i-1] == s2[j-1], then dp[i][j] = dp[i-1][j-1] + 1.
3. Otherwise, dp[i][j] = 0 (substring must be contiguous).
4. Track the maximum value in the dp table.

class Solution {
    public static int longestCommonSubstring(String s1, String s2) {
        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;
                }
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        String s1 = "ABCDGH";
        String s2 = "ACDGHR";
        System.out.println(longestCommonSubstring(s1, s2)); // Output: 4
    }
}

Complexity Analysis

• Time Complexity: O(m * n) - filling the 2D table
• Space Complexity: O(m * n) - the dp table