Longest Common Substring

Problem Link

Longest Common Substring – GeeksforGeeks (GeeksforGeeks)

Problem Statement

Given two strings s1 (length n) and s2 (length m), return the length of their longest common substring—a contiguous sequence present in both.

Examples:

• Input: s1 = "ABCDGH", s2 = "ACDGHR" → Output: 4 ("CDGH")

• Input: s1 = "abc", s2 = "acb" → Output: 1 (common substrings "a", "b", "c") (GeeksforGeeks)

Intuition

We aim to find the maximum length k such that s1[i−k+1…i] = s2[j−k+1…j] for some i, j.

Choice Diagram

At each pair (i, j) (character positions in s1 and s2):

       if s1[i] == s2[j]:
             length = 1 + LCSuff(i−1, j−1)
       else:
             length = 0  // substring resets on mismatch

We track the global maximum of these lengths.

1. Recursion (IBH)

Function: LCSuff(i, j) = longest suffix ending at i, j

• Base case: if i < 0 or j < 0, return 0.

• If match: return 1 + LCSuff(i−1, j−1).

• Else: return 0 (substring must be contiguous).

To get the answer, call LCSuff(i, j) for all 0 ≤ i < n, 0 ≤ j < m and track the maximum.

class Solution {
    int maxAns = 0;

    public int longestCommonSubstrRec(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                LCSuff(s1, s2, i, j);
            }
        }
        return maxAns;
    }

    private int LCSuff(String s1, String s2, int i, int j) {
        if (i < 0 || j < 0) return 0;

        int res = 0;
        if (s1.charAt(i) == s2.charAt(j)) {
            res = 1 + LCSuff(s1, s2, i - 1, j - 1);
            maxAns = Math.max(maxAns, res);
        }
        return res;
    }
}

Time: O(n*m*min(n,m)) (expensive)
Space: O(n + m) due to recursion depth

2. Memoization (Top-Down DP)

Add a 2D array to cache LCSuff(i, j) results.

class Solution {
    int maxAns = 0;
    int[][] dp;

    public int longestCommonSubstrMem(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        dp = new int[n][m];
        for (int[] row : dp) Arrays.fill(row, -1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                LCSuff(s1, s2, i, j);
            }
        }
        return maxAns;
    }

    private int LCSuff(String s1, String s2, int i, int j) {
        if (i < 0 || j < 0) return 0;
        if (dp[i][j] != -1) return dp[i][j];

        if (s1.charAt(i) == s2.charAt(j)) {
            dp[i][j] = 1 + LCSuff(s1, s2, i - 1, j - 1);
            maxAns = Math.max(maxAns, dp[i][j]);
        } else {
            dp[i][j] = 0;
        }
        return dp[i][j];
    }
}

Time: O(n * m)
Space: O(n * m) + O(n + m)

3. Tabulation (Bottom-Up DP)

Construct a 2D dp[n+1][m+1] array by treating indices 1 to n, 1 to m.

• If s1[i-1] == s2[j-1]: dp[i][j] = 1 + dp[i-1][j-1]

• Else: dp[i][j] = 0
  Track maxAns during table fill.

class Solution {
    public int longestCommonSubstrTab(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[][] dp = new int[n + 1][m + 1];
        int maxAns = 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];
                    maxAns = Math.max(maxAns, dp[i][j]);
                }
            }
        }
        return maxAns;
    }
}

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

4. Space Optimization

Notice only dp[i-1][j-1] is needed to compute dp[i][j]. Use two 1D arrays of size m+1.

class Solution {
    public int longestCommonSubstrSO(String s1, String s2) {
        int n = s1.length(), m = s2.length();
        int[] prev = new int[m + 1], curr = new int[m + 1];
        int maxAns = 0;

        for (int i = 1; i <= n; i++) {
            Arrays.fill(curr, 0);
            for (int j = 1; j <= m; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    curr[j] = 1 + prev[j - 1];
                    maxAns = Math.max(maxAns, curr[j]);
                }
            }
            int[] temp = prev;
            prev = curr;
            curr = temp;
        }
        return maxAns;
    }
}

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

Complexity Summary