Longest Common Substring in DSA Javascript - Execution Trace

Concept Flow - Longest Common Substring

Start with two strings

↓

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

↓

Initialize all cells to 0

↓

For each character in string1 (i)

↓

For each character in string2 (j)

↓

If chars match: table[i

↓

Update max length and end position if needed

↓

Else: table[i

↓

After filling table, extract substring from end position

↓

Return longest common substring

↓

Done

We build a table to track matching characters between two strings. When characters match, we extend the substring length from the previous diagonal cell. We keep track of the longest length and its position to extract the substring at the end.

Execution Sample

DSA Javascript

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

This code finds the longest substring common to both input strings by building a table of matching character lengths and tracking the maximum length and position.

Execution Table

Step	Operation	i	j	Chars Compared	table[i][j]	maxLen	endPos	Visual State (table row i)
1	Initialize table with zeros	-	-	-	-	0	0	[0,0,0,0]
2	Compare s1[0]='a' and s2[0]='b'	1	1	'a' vs 'b'	0	0	0	[0,0,0,0]
3	Compare s1[0]='a' and s2[1]='a'	1	2	'a' vs 'a'	1	1	1	[0,0,1,0]
4	Compare s1[0]='a' and s2[2]='c'	1	3	'a' vs 'c'	0	1	1	[0,0,1,0]
5	Compare s1[1]='b' and s2[0]='b'	2	1	'b' vs 'b'	1	1	1	[0,1,0,0]
6	Compare s1[1]='b' and s2[1]='a'	2	2	'b' vs 'a'	0	1	1	[0,1,0,0]
7	Compare s1[1]='b' and s2[2]='c'	2	3	'b' vs 'c'	0	1	1	[0,1,0,0]
8	Compare s1[2]='c' and s2[0]='b'	3	1	'c' vs 'b'	0	1	1	[0,0,0,0]
9	Compare s1[2]='c' and s2[1]='a'	3	2	'c' vs 'a'	0	1	1	[0,0,0,0]
10	Compare s1[2]='c' and s2[2]='c'	3	3	'c' vs 'c'	table[2][2]+1=1	1	3	[0,0,0,1]
11	No update (1 not > maxLen)	-	-	-	-	1	3	[0,0,0,1]
12	Compare s1[3]='d' and s2[0]='b'	4	1	'd' vs 'b'	0	1	3	[0,0,0,0]
13	Compare s1[3]='d' and s2[1]='a'	4	2	'd' vs 'a'	0	1	3	[0,0,0,0]
14	Compare s1[3]='d' and s2[2]='c'	4	3	'd' vs 'c'	0	1	3	[0,0,0,0]
15	End of loops	-	-	-	-	1	3	Table complete

💡 All characters compared; maxLen=1 at endPos=3; longest common substring is 'c' (s1.slice(2,3))

Variable Tracker

Variable	Start	After Step 3	After Step 10	After Step 11	Final
maxLen	0	1	1	1	1
endPos	0	1	3	3	3

Key Moments - 3 Insights

Why do we add 1 to table[i-1][j-1] when characters match?

Because table[i-1][j-1] stores the length of the common substring ending at previous characters. Adding 1 extends that substring by one matching character (see step 10 in execution_table).

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

Because the substring must be continuous. A mismatch breaks the substring, so length resets to 0 at that position (see steps 2,4,6 in execution_table).

How do we know where the longest substring ends?

We track endPos whenever we find a longer substring (step 3). This position marks the end index in s1 to extract the substring after the loops.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the value of table[3][3]?

A 0

B 1

C 2

D 3

💡 Hint

Check the 'table[i][j]' column at step 10 in execution_table.

At which step does maxLen get updated to 1 for the first time?

A Step 3

B Step 5

C Step 10

D Step 11

💡 Hint

Look at the maxLen column in execution_table rows and when it changes from 0 to 1.

If s1 was 'abc' and s2 was 'abc', what would table[3][3] be after filling?

A 1

B 2

C 3

D 0

💡 Hint

Longest common substring length equals the length of the entire string if both are identical.

Concept Snapshot

Longest Common Substring finds the longest continuous matching part between two strings.
Use a 2D table where table[i][j] stores length of common substring ending at s1[i-1] and s2[j-1].
If chars match: table[i][j] = table[i-1][j-1] + 1, else 0.
Track max length and end position to extract substring after filling table.
Time complexity: O(m*n), space complexity: O(m*n).

Full Transcript

Longest Common Substring problem is solved by comparing two strings character by character and building a table that stores lengths of matching substrings ending at each position. We initialize a 2D table with zeros. For each character pair, if they match, we set the current cell to one plus the diagonal previous cell. If not, we reset to zero. 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 position and length. This approach ensures we find the longest continuous substring common to both strings efficiently.

Practice

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

easy

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

B. The longest sequence of characters that appear anywhere in both strings, not necessarily consecutively

C. The total number of common characters between two strings

D. The longest sequence of characters that appear consecutively in both strings

Solution

1. Step 1: Understand the problem definition

   The Longest Common Substring problem looks for the longest continuous sequence of characters shared by both strings.

2. Step 2: Differentiate from similar problems

   Unlike Longest Common Subsequence, the substring must be consecutive characters, not scattered.

3. Final Answer:

   The longest sequence of characters that appear consecutively in both strings -> Option D

4. Quick Check:

   Longest Common Substring = consecutive matching characters [OK]

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

Common Mistakes:

• Confusing substring with subsequence
• Thinking order does not matter
• Ignoring continuity requirement

2. Which of the following JavaScript code snippets correctly initializes a 2D array for dynamic programming in Longest Common Substring?

easy

A. const dp = Array(m + 1).fill(Array(n + 1).fill(0));

B. const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

C. const dp = new Array(m + 1).fill(new Array(n + 1).fill(0));

D. const dp = Array(m + 1).map(Array(n + 1).fill(0));

Solution

1. Step 1: Understand 2D array initialization in JavaScript

   Using Array.from with a mapping function creates independent inner arrays, avoiding shared references.

2. Step 2: Analyze each option

   Options B and C use fill with arrays, causing all rows to reference the same inner array. const dp = Array(m + 1).map(Array(n + 1).fill(0)); passes Array(n + 1).fill(0) directly to map, which expects a function and causes TypeError.

3. Final Answer:

   const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); -> Option B

4. Quick Check:

   Use Array.from with function for independent rows [OK]

Hint: Use Array.from with function to avoid shared inner arrays [OK]

Common Mistakes:

• Using fill with arrays causing shared references
• Using map on uninitialized arrays
• Not initializing inner arrays properly

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

function longestCommonSubstring(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  let maxLen = 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: Trace matching characters between 'abcde' and 'abfde'

   Matching substrings are 'ab' at start and 'de' at end. Both have length 2.

2. Step 2: Identify longest common substring length

   Longest common substring length is 2, from either 'ab' or 'de'.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Longest common substring length = 2 [OK]

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

Common Mistakes:

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

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

function lcsLength(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array(m + 1).fill(Array(n + 1).fill(0));
  let maxLen = 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. dp array rows share the same inner array causing incorrect updates

B. Loop indices start from 1 instead of 0 causing index errors

C. The maxLen variable is not updated inside the loop

D. The function returns dp[m][n] instead of maxLen

Solution

1. Step 1: Analyze dp array initialization

   Using fill with an array causes all rows to reference the same inner array, so updates affect all rows.

2. Step 2: Understand impact on dp updates

   Because rows share the same array, dp[i][j] updates overwrite other rows, corrupting the dp table and results.

3. Final Answer:

   dp array rows share the same inner array causing incorrect updates -> Option A

4. Quick Check:

   Shared inner arrays cause dp corruption [OK]

Hint: Avoid fill with arrays; use Array.from with function [OK]

Common Mistakes:

• Using fill for 2D arrays causing shared references
• Ignoring dp table corruption
• Misunderstanding loop indices

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

hard

A. 'xab', length 3

B. 'abx', length 3

C. 'abxa', length 4

D. 'abc', length 3

Solution

1. Step 1: Identify common substrings between s1 and s2

   Check substrings of s1 in s2: 'xab' appears, 'abx' appears, 'abxa' appears in s2 starting at index 4.

2. Step 2: Find the longest continuous match

   'abxa' is length 4 and appears in both strings continuously, longer than other matches.

3. Final Answer:

   'abxa', length 4 -> Option C

4. Quick Check:

   Longest common substring = 'abxa' length 4 [OK]

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

Common Mistakes:

• Choosing shorter substrings ignoring longer matches
• Confusing substring with subsequence
• Missing overlapping matches