Longest Common Substring in DSA C++

Mental Model

Find the longest sequence of characters that appears exactly the same in both strings without skipping any characters.

Analogy: Imagine two friends reading two different books and trying to find the longest exact phrase that appears in both books without any gaps.

String1: a b c d e f g h
String2: x y a b c z h i j

Matrix:
    x y a b c z h i j
  0 0 0 0 0 0 0 0 0 0
a 0 0 0 ↑1 0 0 0 0 0
b 0 0 0 0 ↑2 0 0 0 0
c 0 0 0 0 0 ↑3 0 0 0
...

Dry Run Walkthrough

Input: String1: "abcde", String2: "abfde"

Goal: Find the longest substring that appears in both strings exactly.

Step 1: Initialize a 2D matrix of size (len(String1)+1) x (len(String2)+1) with zeros

Matrix with all zeros:
  0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Why: We use this matrix to store lengths of common substrings ending at each pair of indices.

Step 2: Compare characters String1[0] = 'a' and String2[0] = 'a', they match, set matrix[1][1] = 1

Matrix:
  0 0 0 0 0 0
0 1 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Why: Matching characters start a substring of length 1.

Step 3: Compare String1[1] = 'b' and String2[1] = 'b', match, set matrix[2][2] = matrix[1][1] + 1 = 2

Matrix:
  0 0 0 0 0 0
0 1 0 0 0 0
0 0 2 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Why: Continuing substring increases length by 1.

Step 4: Compare String1[2] = 'c' and String2[2] = 'f', no match, set matrix[3][3] = 0

Matrix:
  0 0 0 0 0 0
0 1 0 0 0 0
0 0 2 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Why: No match breaks the substring, reset length to 0.

Step 5: Compare String1[3] = 'd' and String2[3] = 'd', match, set matrix[4][4] = matrix[3][3] + 1 = 1

Matrix:
  0 0 0 0 0 0
0 1 0 0 0 0
0 0 2 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 0

Why: New matching substring starts here.

Step 6: Compare String1[4] = 'e' and String2[4] = 'e', match, set matrix[5][5] = matrix[4][4] + 1 = 2

Matrix:
  0 0 0 0 0 0
0 1 0 0 0 0
0 0 2 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
0 0 0 0 0 2

Why: Continuing substring increases length by 1.

Result:

Longest common substring length is 2, substrings: "ab" or "de"

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <string>
using namespace std;

string longestCommonSubstring(const string &s1, const string &s2) {
    int n = s1.size();
    int m = s2.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    int maxLen = 0;
    int endIndex = 0; // end index of substring in s1

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1; // extend substring
                if (dp[i][j] > maxLen) {
                    maxLen = dp[i][j];
                    endIndex = i - 1;
                }
            } else {
                dp[i][j] = 0; // reset on mismatch
            }
        }
    }
    if (maxLen == 0) return "";
    return s1.substr(endIndex - maxLen + 1, maxLen);
}

int main() {
    string s1 = "abcde";
    string s2 = "abfde";
    string result = longestCommonSubstring(s1, s2);
    cout << "Longest Common Substring: " << result << "\n";
    return 0;
}

dp[i][j] = dp[i - 1][j - 1] + 1; // extend substring

extend current matching substring length by 1

if (dp[i][j] > maxLen) { maxLen = dp[i][j]; endIndex = i - 1; }

update max length and end index when longer substring found

dp[i][j] = 0; // reset on mismatch

reset substring length to zero when characters differ

Output

Longest Common Substring: ab

Complexity Analysis

Time: O(n*m) because we fill a matrix of size n by m comparing all character pairs once

Space: O(n*m) because we store substring lengths for all pairs in a 2D matrix

vs Alternative: Naive approach checks all substrings which is O(n^3), dynamic programming reduces it to O(n*m)

Edge Cases

One or both strings empty

Returns empty string as no common substring exists

DSA C++

if (maxLen == 0) return "";

No common substring

Returns empty string because no matching characters found

DSA C++

if (maxLen == 0) return "";

Strings are identical

Returns the entire string as longest common substring

DSA C++

dp[i][j] = dp[i - 1][j - 1] + 1;

When to Use This Pattern

When you need to find the longest exact matching sequence inside two strings, use the longest common substring pattern with dynamic programming to efficiently track matching lengths.

Common Mistakes

Mistake: Confusing longest common substring with longest common subsequence which allows gaps
Fix: Remember substring requires continuous characters, so reset count on mismatch

Mistake: Not updating max length and end index correctly, leading to wrong substring output
Fix: Update maxLen and endIndex inside the matching condition whenever a longer substring is found

Summary

Finds the longest continuous sequence of characters common to both strings.

Use when you want the longest exact matching substring without gaps between characters.

Track lengths of matching substrings ending at each pair of indices and reset on mismatch.

Practice

1. What does the Longest Common Substring problem find between two strings s1 and s2?

easy

A. The longest sequence of characters that appear contiguously in both strings

B. The longest sequence of characters that appear in both strings but not necessarily contiguously

C. The total number of common characters between the two strings

D. The longest string formed by concatenating both strings

Solution

1. Step 1: Understand the problem definition

   The Longest Common Substring problem looks for the longest continuous sequence of characters that appears in both strings without any breaks.

2. Step 2: Differentiate from similar problems

   Unlike Longest Common Subsequence, which allows gaps, Longest Common Substring requires characters to be contiguous in both strings.

3. Final Answer:

   The longest sequence of characters that appear contiguously in both strings -> Option A

4. Quick Check:

   Longest Common Substring = contiguous matching characters [OK]

Hint: Look for continuous matching characters in both strings [OK]

Common Mistakes:

• Confusing substring with subsequence
• Thinking characters can be non-contiguous
• Counting total common characters instead of longest continuous

2. Which of the following C++ code snippets correctly initializes a 2D vector dp of size m+1 by n+1 with all zeros for Longest Common Substring?

easy

A. std::vector dp(m+1, std::vector<int>(n+1, 0));

B. std::vector<int> dp(m+1, std::vector<int>(n+1, 0));

C. std::vector dp(m, std::vector<int>(n));

D. std::vector dp(m+1, n+1, 0);

Solution

1. Step 1: Understand 2D vector initialization syntax

   To create a 2D vector with m+1 rows and n+1 columns filled with zeros, use nested vector initialization.

2. Step 2: Check each option

   std::vector dp(m+1, std::vector<int>(n+1, 0)); correctly creates a vector of vectors with m+1 rows, each row a vector of n+1 zeros. Others have syntax errors or wrong types.

3. Final Answer:

   std::vector dp(m+1, std::vector<int>(n+1, 0)); -> Option A

4. Quick Check:

   Correct 2D vector initialization = std::vector dp(m+1, std::vector<int>(n+1, 0)); [OK]

Hint: Use nested vector constructor for 2D zero initialization [OK]

Common Mistakes:

• Using wrong vector types in initialization
• Missing inner vector initialization
• Trying to pass three arguments to vector constructor

3. What is the output of the following C++ code snippet?

std::string s1 = "abcdxyz";
std::string s2 = "xyzabcd";
int m = s1.size(), n = s2.size();
std::vector dp(m+1, std::vector<int>(n+1, 0));
int maxLen = 0;
for (int i = 1; i <= m; i++) {
  for (int j = 1; j <= n; j++) {
    if (s1[i-1] == s2[j-1]) {
      dp[i][j] = dp[i-1][j-1] + 1;
      maxLen = std::max(maxLen, dp[i][j]);
    }
  }
}
std::cout << maxLen << std::endl;

medium

A. 3

B. 4

C. 1

D. 0

Solution

1. Step 1: Trace matching substrings

   The longest common substring is "abcd" (length 4), which appears contiguously at the start of s1 and end of s2. "xyz" is length 3.

2. Step 2: Check dp updates and maxLen

   dp updates length for matching characters. The longest continuous match found is length 4 for "abcd".

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Longest common substring length = 4 [OK]

Hint: Check continuous matching segments, not total matches [OK]

Common Mistakes:

• Confusing substring with subsequence length
• Counting non-contiguous matches
• Off-by-one errors in indexing

4. Identify the bug in the following C++ code snippet for Longest Common Substring:

std::string s1 = "abcde";
std::string s2 = "abfde";
int m = s1.size(), n = s2.size();
std::vector dp(m+1, std::vector<int>(n+1, 0));
int maxLen = 0;
for (int i = 1; i <= m; i++) {
  for (int j = 1; j <= n; j++) {
    if (s1[i] == s2[j]) {
      dp[i][j] = dp[i-1][j-1] + 1;
      maxLen = std::max(maxLen, dp[i][j]);
    }
  }
}
std::cout << maxLen << std::endl;

medium

A. dp vector size should be (m+1) x (n+1) to avoid out-of-bound errors

B. maxLen should be initialized to -1 instead of 0

C. The loop indices should start from 0 instead of 1

D. The comparison should be s1[i-1] == s2[j-1] instead of s1[i] == s2[j]

Solution

1. Step 1: Check string indexing inside loops

   Loop variables i and j start from 1, so to access string characters correctly, indices should be i-1 and j-1.

2. Step 2: Identify the incorrect comparison

   The code compares s1[i] and s2[j], which causes out-of-bound access and wrong comparisons. It should be s1[i-1] == s2[j-1].

3. Final Answer:

   The comparison should be s1[i-1] == s2[j-1] instead of s1[i] == s2[j] -> Option D

4. Quick Check:

   Correct string indexing = i-1 and j-1 [OK]

Hint: Use i-1 and j-1 to index strings when loops start at 1 [OK]

Common Mistakes:

• Accessing string with i or j directly causing out-of-bounds
• Not initializing dp with correct size
• Starting loops at wrong indices

5. Given two strings s1 = "banana" and s2 = "ananas", write a C++ function to find the longest common substring and return it. What is the correct longest common substring?

hard

A. "anana"

B. "nana"

C. "ana"

D. "ban"

Solution

1. Step 1: Understand the longest common substring candidates

   Check substrings common to both strings. "ana" (length 3) appears multiple times in both strings. "anana" is not a substring of both strings contiguously.

2. Step 2: Verify other options

   "nana" length 4 is not a substring of s2; "ban" only in s1; "anana" is not a substring of s2.

3. Final Answer:

   "ana" -> Option C

4. Quick Check:

   Longest common substring between "banana" and "ananas" is "ana" [OK]

Hint: Check all continuous matches, pick longest common substring [OK]

Common Mistakes:

• Choosing longest common subsequence instead of substring
• Ignoring continuity requirement
• Assuming longer substrings without verifying presence