Longest Common Substring in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

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

DSA Typescript

const dp: number[][] = Array([1]).fill(0).map(() => Array(m + 1).fill(0));

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

Am + 1

Bn

Cn + 1

Dm

Attempts:

3 left

💡 Hint

Common Mistakes

Using m+1 instead of n+1 for rows.

Not adding 1 to the length causing index errors.

We create a 2D array with (n+1) rows to cover all prefixes of the first string including empty prefix.

2fill in blank

medium

Complete the code to update the dp table when characters match.

DSA Typescript

if (s1[i - 1] === s2[j - 1]) {
  dp[i][j] = dp[i - 1][[1]] + 1;
} else {
  dp[i][j] = 0;
}

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

Aj - 1

Bj

Cj + 1

Dj - 2

Attempts:

3 left

💡 Hint

Common Mistakes

Using dp[i-1][j] or dp[i][j-1] instead of dp[i-1][j-1].

Adding 1 to the wrong index.

When characters match, we extend the substring by 1 from the previous diagonal cell dp[i-1][j-1].

3fill in blank

hard

Fix the error in updating the maximum length of the longest common substring.

DSA Typescript

if (dp[i][j] > [1]) {
  maxLen = dp[i][j];
  endIndex = i;
}

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

AendIndex

Bi

Cj

DmaxLen

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with endIndex instead of maxLen.

Using i or j as comparison variable.

We compare dp[i][j] with maxLen to update the maximum length found so far.

4fill in blank

hard

Fill both blanks to extract the longest common substring from s1.

DSA Typescript

const longestSubstring = s1.slice([1], [2]);

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

AendIndex - maxLen

BmaxLen

CendIndex

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using maxLen as start index.

Using 0 as start index instead of calculated start.

We slice s1 from (endIndex - maxLen) to endIndex to get the longest common substring.

5fill in blank

hard

Fill all three blanks to complete the nested loops for dp table computation.

DSA Typescript

for (let i = 1; i <= [1]; i++) {
  for (let j = 1; j <= [2]; j++) {
    if (s1[i - 1] === s2[j - 1]) {
      dp[i][j] = dp[i - 1][j - 1] + [3];
    } else {
      dp[i][j] = 0;
    }
  }
}

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

An

Bm

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 as increment instead of 1.

Swapping n and m in loops.

The outer loop runs from 1 to n, inner loop from 1 to m, and we add 1 when characters match.