Longest Common Substring in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Common Substring Length Calculation

What is the output of the following TypeScript code that calculates the length of the longest common substring between two strings?

DSA Typescript

function longestCommonSubstring(s1: string, s2: string): number {
  const m = s1.length;
  const n = s2.length;
  let maxLen = 0;
  const dp: number[][] = Array(m + 1).fill(null).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;
        if (dp[i][j] > maxLen) {
          maxLen = dp[i][j];
        }
      }
    }
  }
  return maxLen;
}

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

A 4

B 3

C 2

D 1

💡 Hint

Check the longest sequence of matching characters in order.

The longest common substring between "abcde" and "abfde" is "ab" which has length 2.

🧠 Conceptual

intermediate

Understanding the Longest Common Substring Concept

Which of the following best describes the longest common substring between two strings?

A The longest sequence of characters that appear in both strings in the same order and contiguously.

B The longest sequence of characters that appear in both strings in any order, not necessarily contiguous.

C The longest sequence of characters that appear in both strings but can be separated by other characters.

D The longest sequence of characters that appear only in the first string.

💡 Hint

Think about continuous matching characters.

The longest common substring requires characters to be contiguous and in the same order in both strings.

❓ Predict Output

advanced

Output of Longest Common Substring with Empty String

What is the output of this TypeScript code when one input string is empty?

DSA Typescript

function longestCommonSubstring(s1: string, s2: string): number {
  const m = s1.length;
  const n = s2.length;
  let maxLen = 0;
  const dp: number[][] = Array(m + 1).fill(null).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;
        if (dp[i][j] > maxLen) {
          maxLen = dp[i][j];
        }
      }
    }
  }
  return maxLen;
}

console.log(longestCommonSubstring("", "abc"));

A 3

B 0

C 1

D undefined

💡 Hint

If one string is empty, no common substring exists.

Since one string is empty, there can be no common substring, so the length is 0.

🔧 Debug

advanced

Identify the Error in Longest Common Substring Code

What error will this TypeScript code produce when run?

DSA Typescript

function longestCommonSubstring(s1: string, s2: string): number {
  const m = s1.length;
  const n = s2.length;
  let maxLen = 0;
  const dp: number[][] = Array(m).fill(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;
        if (dp[i][j] > maxLen) {
          maxLen = dp[i][j];
        }
      }
    }
  }
  return maxLen;
}

console.log(longestCommonSubstring("abc", "abc"));

A SyntaxError: Unexpected token '['

B ReferenceError: dp is not defined

C Output: 3

D TypeError: Cannot set property '1' of undefined

💡 Hint

Check how the 2D array dp is initialized.

The dp array is initialized incorrectly using fill with the same inner array reference, causing undefined errors when assigning dp[i][j].

🚀 Application

expert

Longest Common Substring Length for Large Inputs

Given two strings each of length 1000 consisting of only 'a' characters, what is the length of their longest common substring?

A 1000

B 1

C 0

D 999

💡 Hint

All characters match continuously.

Since both strings are identical and consist only of 'a's, the entire string is the longest common substring.