A common mistake is confusing Longest Common Subsequence with Longest Common Substring.
Subsequence → characters can skip.
Substring → characters must be continuous.
In this problem, we need the Longest Common Substring.
Practice Leetcode : https://leetcode.com/problems/maximum-length-of-repeated-subarray/submissions/1983173785/
Problem Statement
Given two strings s1 and s2, return the length of their longest common substring.
Example:
Input:
s1 = "abcjklp"`
s2 = "acjkp"
Output: 3
Explanation:
Longest common substring = "cjk"
- Recursive Solution(Brute Force)
Idea:
At every (i, j):
If characters match → continue substring count.
Else reset count = 0.
Also explore skipping one char from either string.
class Solution {
public int longCommSubstr(String s1, String s2) {
return solve(s1, s2, s1.length(), s2.length(), 0);
}
int solve(String s1, String s2, int i, int j, int count) {
if (i == 0 || j == 0) return count;
int same = count;
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
same = solve(s1, s2, i - 1, j - 1, count + 1);
}
int skip1 = solve(s1, s2, i - 1, j, 0);
int skip2 = solve(s1, s2, i, j - 1, 0);
return Math.max(same, Math.max(skip1, skip2));
}
}
Time Complexity:
O(3^(n+m)) (very slow)
2.Memoization(Top Down DP)
We memoize states (i, j, count).
class Solution {
Integer[][][] dp;
public int longCommSubstr(String s1, String s2) {
int n = s1.length(), m = s2.length();
dp = new Integer[n + 1][m + 1][Math.min(n, m) + 1];
return solve(s1, s2, n, m, 0);
}
int solve(String s1, String s2, int i, int j, int count) {
if (i == 0 || j == 0) return count;
if (dp[i][j][count] != null) return dp[i][j][count];
int same = count;
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
same = solve(s1, s2, i - 1, j - 1, count + 1);
}
int skip1 = solve(s1, s2, i - 1, j, 0);
int skip2 = solve(s1, s2, i, j - 1, 0);
return dp[i][j][count] = Math.max(same, Math.max(skip1, skip2));
}
}
Time Complexity:
O(n * m * min(n,m))
- Tabulation (Bottom Up DP)
Core Transition:
If chars match:
dp[i][j] = 1 + dp[i-1][j-1]
Else:
dp[i][j] = 0
Because substring must be continuous.
class Solution {
public int longCommSubstr(String s1, String s2) {
int n = s1.length(), m = s2.length();
int[][] dp = new int[n + 1][m + 1];
int max = 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];
max = Math.max(max, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return max;
}
}
- Space Optimized DP (Best Solution)
Since only previous row is needed.
Code (Optimized)
class Solution {
public int longCommSubstr(String s1, String s2) {
return longestCommonSubstring(s1, s2);
}
public int longestCommonSubstring(String s, String t) {
int n = s.length(), m = t.length();
int[] prev = new int[m + 1];
int max = 0;
for (int i = 1; i <= n; i++) {
int[] cur = new int[m + 1];
for (int j = 1; j <= m; j++) {
if (s.charAt(i - 1) == t.charAt(j - 1)) {
cur[j] = 1 + prev[j - 1];
max = Math.max(max, cur[j]);
} else {
cur[j] = 0;
}
}
prev = cur;
}
return max;
}
}
Why 0 on mismatch?
Because substring must be continuous.
If characters break:
abc
abx
At c != x, chain breaks completely.
So: dp[i][j] = 0
Complexity Comparison
-
Recursion
Exponential | O(n+m) -
*Memoization *
O(nmk) | O(nmk) -
Tabulation
O(n*m) | O(n*m) -
Space Optimized
O(n*m) | O(m)