Longest Common Substring in DSA Typescript - Execution Trace

Concept Flow - Longest Common Substring

Start with two strings

↓

Create 2D table of size (m+1)x(n+1)

↓

Initialize first row and column to 0

↓

For each character pair (i,j):

↓

If chars match: table[i

↓

Update max length and position if needed

↓

If chars don't match: table[i

↓

After filling table, extract substring from max position

↓

Return longest common substring

We build a table to track matching characters between two strings. When characters match, we extend the substring length. We keep track of the longest substring found.

Execution Sample

DSA Typescript

function longestCommonSubstring(s1: string, s2: string): string {
  const m = s1.length, n = s2.length;
  const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
  let maxLen = 0, endIndex = 0;
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        if (dp[i][j] > maxLen) {
          maxLen = dp[i][j];
          endIndex = i;
        }
      } else {
        dp[i][j] = 0;
      }
    }
  }
  return s1.slice(endIndex - maxLen, endIndex);
}

This code finds the longest common substring between two strings by building a 2D table of substring lengths. Example: longestCommonSubstring('abcde', 'bacd') returns 'cd'.

Execution Table

Step	i,j	Characters Compared	dp[i][j]	Max Length	End Index	Visual dp Table Row (i)
1	1,1	s1[0]='a' vs s2[0]='b'	0	0	0	[0,0,0,0,0]
2	1,2	s1[0]='a' vs s2[1]='a'	1	1	1	[0,0,1,0,0]
3	1,3	s1[0]='a' vs s2[2]='c'	0	1	1	[0,0,1,0,0]
4	1,4	s1[0]='a' vs s2[3]='d'	0	1	1	[0,0,1,0,0]
5	2,1	s1[1]='b' vs s2[0]='b'	1	1	1	[0,1,0,0,0]
6	2,2	s1[1]='b' vs s2[1]='a'	0	1	1	[0,1,0,0,0]
7	2,3	s1[1]='b' vs s2[2]='c'	0	1	1	[0,1,0,0,0]
8	2,4	s1[1]='b' vs s2[3]='d'	0	1	1	[0,1,0,0,0]
9	3,1	s1[2]='c' vs s2[0]='b'	0	1	1	[0,0,0,0,0]
10	3,2	s1[2]='c' vs s2[1]='a'	0	1	1	[0,0,0,0,0]
11	3,3	s1[2]='c' vs s2[2]='c'	1	1	1	[0,0,1,0,0]
12	3,4	s1[2]='c' vs s2[3]='d'	0	1	1	[0,0,1,0,0]
13	4,1	s1[3]='d' vs s2[0]='b'	0	1	1	[0,0,0,0,0]
14	4,2	s1[3]='d' vs s2[1]='a'	0	1	1	[0,0,0,0,0]
15	4,3	s1[3]='d' vs s2[2]='c'	0	1	1	[0,0,0,0,0]
16	4,4	s1[3]='d' vs s2[3]='d'	2	2	4	[0,0,0,0,2]
17	5,1	s1[4]='e' vs s2[0]='b'	0	2	4	[0,0,0,0,0]
18	5,2	s1[4]='e' vs s2[1]='a'	0	2	4	[0,0,0,0,0]
19	5,3	s1[4]='e' vs s2[2]='c'	0	2	4	[0,0,0,0,0]
20	5,4	s1[4]='e' vs s2[3]='d'	0	2	4	[0,0,0,0,0]
21	End	All pairs checked	-	2	4	Final dp table filled

💡 All character pairs compared; longest substring length found is 2 ending at index 4 in s1 (returns s1.slice(2,4) = 'cd').

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 11	After Step 16	Final
maxLen	0	1	1	1	2	2
endIndex	0	1	1	1	4	4
i	0	1	2	3	4	5
j	0	2	1	3	4	4

Key Moments - 3 Insights

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

Because the substring must be continuous, a mismatch breaks the substring, so dp[i][j] is 0. See execution_table rows 1,3,4 where dp[i][j] is set to 0 after mismatch.

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

Because a matching character extends the previous substring by 1. This is shown in execution_table rows 2,5,11,16 where dp[i][j] builds on dp[i-1][j-1].

How do we know where the longest substring ends?

We track endIndex whenever maxLen updates (if dp[i][j] > maxLen). For example, after step 16, endIndex is 4, meaning substring ends at s1[3] (0-based index).

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is dp[2][1] and what does it represent?

A dp[2][1] = 0, representing no match

B dp[2][1] = 2, representing substring length 2

C dp[2][1] = 1, representing a matching character extending substring

D dp[2][1] = -1, invalid value

💡 Hint

Check execution_table row 5 under dp[i][j] column

At which step does the maxLen first update to 1?

A Step 1

B Step 2

C Step 5

D Step 11

💡 Hint

Look at maxLen column in execution_table rows 1 and 2

If s1[3] was 'c' instead of 'd', how would dp[4][4] change at step 16?

A dp[4][4] would be 0 because characters don't match

B dp[4][4] would be 2 because characters match and extend substring

C dp[4][4] would be 1 as before

D dp[4][4] would be undefined

💡 Hint

s1[3]='c' != s2[3]='d', so mismatch: dp[i][j] = 0. Current step 16 matches so dp[4][4]=2.

Concept Snapshot

Longest Common Substring:
- Use 2D dp table of size (m+1)x(n+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 substring 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 the table by comparing characters: if they match, we add 1 to the diagonal cell dp[i-1][j-1]; if not, we reset to 0. We keep track of the maximum length found and the position where it ends. After filling the table, we extract the substring from the first string using the recorded end position and length. This method ensures we find the longest continuous substring shared by both strings.

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 in order but not necessarily contiguously

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

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

D. The shortest substring that contains all characters from both strings

Solution

1. Step 1: Understand substring vs subsequence

   A substring is a continuous part of a string, while a subsequence can skip characters.

2. Step 2: Define Longest Common Substring

   It finds the longest continuous sequence of characters present in both strings.

3. Final Answer:

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

4. Quick Check:

   Longest Common Substring = continuous match [OK]

Hint: Look for continuous matching characters, not scattered ones [OK]

Common Mistakes:

• Confusing substring with subsequence
• Thinking order doesn't matter
• Counting total common characters instead

2. Which of the following TypeScript function signatures correctly represents a function to find the longest common substring length between two strings s1 and s2?

easy

A. function longestCommonSubstring(s1: string, s2: string): number

B. function longestCommonSubstring(s1: number[], s2: number[]): string

C. function longestCommonSubstring(s1: string, s2: string): string[]

D. function longestCommonSubstring(s1: string, s2: string): void

Solution

1. Step 1: Identify input types

   The inputs are two strings, so parameters should be string.

2. Step 2: Identify output type

   The function returns the length of the longest common substring, which is a number.

3. Final Answer:

   function longestCommonSubstring(s1: string, s2: string): number -> Option A

4. Quick Check:

   Input strings, output number length [OK]

Hint: Match input/output types to problem description [OK]

Common Mistakes:

• Using arrays instead of strings as input
• Returning string or array instead of number
• Using void return type mistakenly

3. What is the output of the following TypeScript code?

function longestCommonSubstring(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  let maxLen = 0;
  const dp: number[][] = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        maxLen = Math.max(maxLen, dp[i][j]);
      }
    }
  }
  return maxLen;
}

console.log(longestCommonSubstring('abcde', 'abfde'));

medium

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Compare characters of 'abcde' and 'abfde'

   Matching continuous substrings are 'ab' at start and 'de' at end, both length 2.

2. Step 2: Find longest continuous match

   Longest common substring length is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Longest common substring length = 2 [OK]

Hint: Check continuous matching parts, not scattered matches [OK]

Common Mistakes:

• Counting non-continuous matches
• Confusing longest common subsequence with substring
• Off-by-one errors in indexing

4. The following TypeScript code attempts to find the longest common substring length but has a bug. What is the bug?

function longestCommonSubstring(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  let maxLen = 0;
  const dp: number[][] = Array(m).fill(0).map(() => Array(n).fill(0));
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
        maxLen = Math.max(maxLen, dp[i][j]);
      }
    }
  }
  return maxLen;
}

medium

A. Loop indices should start from 0 instead of 1

B. dp array is initialized with wrong size causing index errors

C. maxLen is not updated inside the loop

D. Comparison uses wrong characters from strings

Solution

1. Step 1: Check dp array initialization

   dp is created with size m x n but accessed with indices up to m and n (1-based), causing out-of-bound errors.

2. Step 2: Correct dp size

   dp should be (m+1) x (n+1) to safely use 1-based indexing in loops.

3. Final Answer:

   dp array is initialized with wrong size causing index errors -> Option B

4. Quick Check:

   dp size must match loop indices [OK]

Hint: Match dp size with loop ranges to avoid index errors [OK]

Common Mistakes:

• Not adding +1 to dp dimensions
• Starting loops at 1 but dp size too small
• Ignoring index out-of-bound runtime errors

5. Given two strings s1 = 'xabxac' and s2 = 'abcabxabcd', what is the length of their longest common substring?

hard

A. 3

B. 5

C. 6

D. 4

Solution

1. Step 1: Identify common substrings

   Common substrings include 'abx' and 'abxa'. 'abxa' is length 4 and appears in both strings.

2. Step 2: Confirm longest substring length

   No longer continuous substring than length 4 exists in both strings.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Longest common substring length = 4 [OK]

Hint: Look for longest continuous matching sequence visually [OK]

Common Mistakes:

• Counting non-continuous matches
• Choosing shorter common substrings
• Confusing substring with subsequence