Log inSign up
mediumGeeksforGeeksNot Started

Longest Common Substring

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on GeeksforGeeks
Lesson

Problem Statement

Given two strings s1 and s2, find the length of the longest common substring.

A substring is a contiguous sequence of characters within a string (unlike a subsequence, which can be non-contiguous).

### Example 1 - Input: s1 = "ABCDGH", s2 = "ACDGHR" - Output: 4 - Explanation: The longest common substring is "CDGH" with length 4.

### Example 2 - Input: s1 = "ABC", s2 = "ACB" - Output: 1 - Explanation: The longest common substrings are "A", "B", and "C", all of length 1.

### Example 3 - Input: s1 = "XYZ", s2 = "ABC" - Output: 0

Constraints:

  • 1 <= s1.length, s2.length <= 1000
  • s1 and s2 consist of uppercase/lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Distinguish between contiguous substring DP and non-contiguous subsequence DP.
  • Reset states to 0 upon character mismatch.
  • Optimize space to O(n) via backward traversal.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Finding longest contiguous common block between two strings.
  • Zeroing out upon mismatch.

Algorithmic Decision Tree:

  • Contiguous -> reset to 0 on mismatch.
  • Answer is global max of table.

Connected Patterns:

Longest Common SubsequenceMaximum Subarray (Kadane)Repeated Substring Pattern

1. All Substrings Generation

Intuition

Generate all substrings of s1 and check if they exist in s2.

Algorithm

  1. For length L from min(m, n) down to 1:
  2. For start from 0 to m - L:
  3. Extract substring sub = s1.substr(start, L).
  4. If s2.find(sub) != string::npos, return L.
  5. Return 0.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5using namespace std;
6
7int longestCommonSubstringBrute(string s1, string s2) {
8 int m = s1.length(), n = s2.length();
9 int maxLen = 0;
10
11 for (int len = min(m, n); len >= 1; len--) {
12 for (int i = 0; i <= m - len; i++) {
13 string sub = s1.substr(i, len);
14 if (s2.find(sub) != string::npos) {
15 return len;
16 }
17 }
18 }
19 return 0;
20}
21
22int main() {
23 string s1 = "ABCDGH", s2 = "ACDGHR";
24 cout << "Longest Common Substring (Brute): " << longestCommonSubstringBrute(s1, s2) << endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(m^2 * n)
  • Space complexity: O(m) substring allocation

2. 2D Dynamic Programming Tabulation

Intuition

Build matrix dp[m + 1][n + 1]. When characters match, extend diagonal dp[i][j] = 1 + dp[i-1][j-1]; else reset to 0.

Algorithm

  1. Let m = s1.length, n = s2.length.
  2. Create dp of size (m + 1) x (n + 1) filled with 0.
  3. Initialize maxLen = 0.
  4. For i = 1 to m:
  5. For j = 1 to n:
  6. If s1[i - 1] == s2[j - 1]:
  7. dp[i][j] = 1 + dp[i - 1][j - 1]
  8. maxLen = max(maxLen, dp[i][j])
  9. Else:
  10. dp[i][j] = 0
  11. Return maxLen.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8int longestCommonSubstring2D(string s1, string s2) {
9 int m = s1.length(), n = s2.length();
10 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
11 int maxLen = 0;
12
13 for (int i = 1; i <= m; i++) {
14 for (int j = 1; j <= n; j++) {
15 if (s1[i - 1] == s2[j - 1]) {
16 dp[i][j] = 1 + dp[i - 1][j - 1];
17 maxLen = max(maxLen, dp[i][j]);
18 } else {
19 dp[i][j] = 0;
20 }
21 }
22 }
23 return maxLen;
24}
25
26int main() {
27 string s1 = "ABCDGH", s2 = "ACDGHR";
28 cout << "Longest Common Substring (2D DP): " << longestCommonSubstring2D(s1, s2) << endl;
29 return 0;
30}

Time & Space Complexity

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

3. 1D Array Backward Tabulation

Intuition

Maintain a single array dp of size n + 1. Traverse j in reverse from n down to 1.

Algorithm

  1. Let m = s1.length, n = s2.length.
  2. Initialize dp of size n + 1 filled with 0.
  3. Initialize maxLen = 0.
  4. For i = 1 to m:
  5. For j = n down to 1:
  6. If s1[i - 1] == s2[j - 1]:
  7. dp[j] = 1 + dp[j - 1]
  8. maxLen = max(maxLen, dp[j])
  9. Else:
  10. dp[j] = 0
  11. Return maxLen.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8int longestCommonSubstringOptimal(string s1, string s2) {
9 if (s1.length() < s2.length()) swap(s1, s2);
10 int m = s1.length(), n = s2.length();
11 vector<int> dp(n + 1, 0);
12 int maxLen = 0;
13
14 for (int i = 1; i <= m; i++) {
15 for (int j = n; j >= 1; j--) {
16 if (s1[i - 1] == s2[j - 1]) {
17 dp[j] = 1 + dp[j - 1];
18 maxLen = max(maxLen, dp[j]);
19 } else {
20 dp[j] = 0;
21 }
22 }
23 }
24 return maxLen;
25}
26
27int main() {
28 string s1 = "ABCDGH", s2 = "ACDGHR";
29 cout << "Longest Common Substring (Optimal 1D DP): " << longestCommonSubstringOptimal(s1, s2) << endl;
30 return 0;
31}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(min(m, n)) space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.All Substrings Brute ForceO(m^2 * n)O(m)Generate all substrings and check presence in s2.Repeated string generation
2.2D TabulationO(m * n)O(m * n)Diagonal matching with reset to 0 on mismatch.Matrix allocation
3.1D Backward TabulationOptimalO(m * n)O(min(m, n))Reverse 1D array traversal with zero resets.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Returning dp[m][n] instead of tracking the global maximum across all cells (the longest substring rarely ends at the very last character of both strings).

Pitfall 2:

Forgetting to set dp[j] = 0 on mismatch in 1D space optimization.

Crucial Edge Cases to Validate:

  • No common characters: Output is 0.
  • Identical strings: Output is length of string.
  • Single character match: Output is 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Ensure you emphasize that the result is max(all dp cells), NOT dp[m][n]! This is the most common mistake candidates make when modifying their LCS code for substrings.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we reset dp[j] to 0 when characters differ in Longest Common Substring, whereas in Longest Common Subsequence we take max(dp[i-1][j], dp[i][j-1])?

Back to DSA Sheet