Longest Common Substring

Time: O(n*m)

Space: O(n*m)

Intuition

DP: dp[i][j] = length of longest common substring ending at s1[i-1] and s2[j-1]. If chars match, dp[i][j]=dp[i-1][j-1]+1. Track global max.

Algorithm

1dp[i][j] = 0 if s1[i-1] != s2[j-1], else dp[i-1][j-1]+1.
2Track max(dp[i][j]) across all i,j.

Example Walkthrough

Input: s1="ABCBDAB", s2="BDCABA"

1.dp fills up. Max common substring is "AB" or "BD" of length 2? Actually "BCB"/"BDCAB" â†’ "BCA"? Let me recalculate: longest = "AB"=2... actually "ABCB" vs "BDCABA" â†’ "AB"=2.

Output: 2

Common Pitfalls

•Unlike LCS, must be contiguous â€” reset dp[i][j]=0 on mismatch, no max with adjacent cells.

Longest Common Substring.java

Java

// Approach: DP. dp[i][j] = length of longest common substring ending at s1[i-1] and s2[j-1].
// Time: O(n*m) Space: O(n*m)
class Solution {
    public int longestCommonSubstr(String str1, String str2) {
        int n = str1.length();
        int m = str2.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 (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                    ans = Math.max(ans, dp[i][j]);
                } else
                    dp[i][j] = 0;
            }
        }

        return ans;
    }
}

Was this solution helpful?