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.