Longest Common Substring in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the 2D array for dynamic programming.

DSA Javascript

const dp = Array(s1.length + 1).fill(null).map(() => Array([1]).fill(0));

Drag options to blanks, or click blank then click option'

As2.length + 1

Bs2.length

Cs1.length

Ds1.length + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using s1.length instead of s2.length for inner array size.

Not adding 1 to lengths for dp array size.

The 2D array dp needs to have rows for each character in s1 plus one extra for empty substring, and columns for s2 length plus one. So dp has dimensions (s1.length + 1) x (s2.length + 1).

2fill in blank

medium

Complete the condition to check if characters match at positions i-1 and j-1.

DSA Javascript

if (s1[i - 1] [1] s2[j - 1]) {

Drag options to blanks, or click blank then click option'

A===

B!==

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using != or !== which check for inequality.

Using == instead of ===.

We use strict equality (===) in JavaScript to check if characters are exactly the same.

3fill in blank

hard

Fix the error in updating dp[i][j] when characters match.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

A/

B-

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition.

Using multiplication or division which are incorrect here.

When characters match, we extend the substring length by 1, so we add 1 to dp[i-1][j-1].

4fill in blank

hard

Fill both blanks to update maxLength and endIndex when a longer substring is found.

DSA Javascript

if (dp[i][j] [1] maxLength) {
  maxLength = dp[i][j];
  endIndex = i [2] 1;
}

Drag options to blanks, or click blank then click option'

A>

B<

C-

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using less than (<) instead of greater than (>).

Adding 1 to i instead of subtracting 1.

We update maxLength if dp[i][j] is greater than current maxLength. endIndex is set to i - 1 because i is 1-based index in dp array.

5fill in blank

hard

Fill all three blanks to return the longest common substring from s1.

DSA Javascript

return s1.slice(endIndex [1] maxLength [2] 1, endIndex [3] 1);

Drag options to blanks, or click blank then click option'

A-

B+

CmaxLength

DendIndex

Attempts:

3 left

💡 Hint

Common Mistakes

Using endIndex - maxLength without adding 1.

Using endIndex - maxLength for end index instead of endIndex + 1.

Confusing maxLength and endIndex in slice parameters.

The slice start index is endIndex - maxLength, and end index is endIndex + maxLength is incorrect. We want endIndex + 1 as end index for slice. So correct is slice(endIndex - maxLength + 1, endIndex + 1). Here blanks fill the start and end indices correctly.

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