Longest Common Substring in DSA C++ - Execution Trace

Concept Flow - Longest Common Substring

Start with two strings

↓

Create 2D table with zeros

↓

For each char in string1

↓

For each char in string2

↓

If chars match

↓

Set table[i

↓

Update max length and position

↓

Else

↓

Set table[i

↓

After filling table

↓

Extract substring from max position

↓

Return longest common substring

We compare characters of both strings, build a table of matching lengths, track the longest match, then extract the substring.

Execution Sample

DSA C++

string s1 = "abcde";
string s2 = "abfde";
int maxLen = 0, endPos = 0;
int dp[6][6] = {0};
// Fill dp and find maxLen
// Extract substring

This code finds the longest common substring between s1 and s2 using a 2D table.

Execution Table

Step	i (s1 index)	j (s2 index)	Chars Compared	dp[i][j]	Max Length	Max End Pos	Visual dp Table State
1	1	1	'a' vs 'a'	1	1	1	[[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]]
2	1	2	'a' vs 'b'	0	1	1	[[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]]
3	1	3	'a' vs 'f'	0	1	1	[[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]]
4	1	4	'a' vs 'd'	0	1	1	[[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]]
5	1	5	'a' vs 'e'	0	1	1	[[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]]
6	2	1	'b' vs 'a'	0	1	1	[[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]]
7	2	2	'b' vs 'b'	1	1	1	[[0,0,0,0,0,0],[0,1,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]]
8	2	3	'b' vs 'f'	0	1	1	[[0,0,0,0,0,0],[0,1,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]]
9	2	4	'b' vs 'd'	0	1	1	[[0,0,0,0,0,0],[0,1,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]]
10	2	5	'b' vs 'e'	0	1	1	[[0,0,0,0,0,0],[0,1,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]]
11	3	1	'c' vs 'a'	0	1	1	[[0,0,0,0,0,0],[0,1,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]]
12	3	2	'c' vs 'b'	0	1	1	[[0,0,0,0,0,0],[0,1,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]]
13	3	3	'c' vs 'f'	0	1	1	[[0,0,0,0,0,0],[0,1,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]]
14	3	4	'c' vs 'd'	0	1	1	[[0,0,0,0,0,0],[0,1,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]]
15	3	5	'c' vs 'e'	0	1	1	[[0,0,0,0,0,0],[0,1,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]]
16	4	1	'd' vs 'a'	0	1	1	[[0,0,0,0,0,0],[0,1,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]]
17	4	2	'd' vs 'b'	0	1	1	[[0,0,0,0,0,0],[0,1,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]]
18	4	3	'd' vs 'f'	0	1	1	[[0,0,0,0,0,0],[0,1,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]]
19	4	4	'd' vs 'd'	1	1	1	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,1,0,0,0],[0,0,0,1,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
20	4	5	'd' vs 'e'	0	1	1	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,1,0,0,0],[0,0,0,1,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
21	5	1	'e' vs 'a'	0	1	1	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,1,0,0,0],[0,0,0,1,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
22	5	2	'e' vs 'b'	0	1	1	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,1,0,0,0],[0,0,0,1,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
23	5	3	'e' vs 'f'	0	1	1	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,1,0,0,0],[0,0,0,1,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
24	5	4	'e' vs 'd'	0	1	1	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,1,0,0,0],[0,0,0,1,0,0],[0,0,0,0,0,0],[0,0,0,0,0,0]]
25	5	5	'e' vs 'e'	1	1	1	[[0,0,0,0,0,0],[0,1,0,0,0,0],[0,0,1,0,0,0],[0,0,0,1,0,0],[0,0,0,0,0,0],[0,0,0,0,0,1]]
26	End	-	-	-	-	-	Completed filling dp table; max length found is 1 at position 1

💡 All characters compared; longest common substring length is 1 ending at index 1 in s1

Variable Tracker

Variable	Start	After Step 1	After Step 7	After Step 19	After Step 25	Final
maxLen	0	1	1	1	1	1
endPos	0	1	1	1	1	1
dp[1][1]	0	1	1	1	1	1
dp[2][2]	0	0	1	1	1	1
dp[4][4]	0	0	0	1	1	1
dp[5][5]	0	0	0	0	1	1

Key Moments - 3 Insights

Why do we set dp[i][j] to 0 when characters don't match?

Because the longest common substring must be continuous. When chars differ, the substring breaks, so dp[i][j] resets to 0 (see steps 2,3,4 in execution_table).

How do we know where the longest substring ends?

We track maxLen and endPos whenever dp[i][j] increases (see steps 1,7,25). endPos marks the index in s1 where the substring ends.

Why do we use dp[i-1][j-1] + 1 when chars match?

Because matching chars extend the previous substring by 1. This builds the length of continuous matching substring diagonally in the table (see step 7).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the value of dp[2][2]?

A 1

B 2

C 0

D 3

💡 Hint

Check the 'dp[i][j]' column at step 7 in execution_table.

At which step does the maxLen first update to 1?

A Step 1

B Step 7

C Step 19

D Step 25

💡 Hint

Look at the 'Max Length' column in execution_table and find when it changes from 0 to 1.

If the characters at s1[3] and s2[3] matched, how would dp[3][3] change at step 13?

A It would be 1

B It would be 0

C It would be dp[2][2] + 1 = 2

D It would be maxLen + 1 = 2

💡 Hint

Recall dp[i][j] = dp[i-1][j-1] + 1 when chars match, see step 7 for example.

Concept Snapshot

Longest Common Substring:
- Use 2D dp table of size (len(s1)+1) x (len(s2)+1)
- dp[i][j] = length of longest substring ending at s1[i-1], s2[j-1]
- If chars match: dp[i][j] = dp[i-1][j-1] + 1
- Else dp[i][j] = 0
- Track max length and end position
- Extract substring from s1 using end position and max length

Full Transcript

Longest Common Substring finds the longest continuous matching part between two strings. We create a 2D table where each cell dp[i][j] stores the length of the longest substring ending at s1[i-1] and s2[j-1]. We fill this table by comparing characters. If they match, we add 1 to the diagonal previous cell. If not, we reset to zero. We keep track of the maximum length found and where it ends in s1. After filling the table, we extract the substring from s1 using the recorded position and length. This method ensures we find the longest continuous matching substring efficiently.

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