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.

Practice

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

easy

A. The longest sequence of characters that appear in order but not necessarily contiguously

B. The total number of common characters between the two strings

C. The longest sequence of characters that appear contiguously in both strings

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

Solution

1. Step 1: Understand substring vs subsequence

   A substring is a continuous part of a string, while a subsequence can skip characters.

2. Step 2: Define Longest Common Substring

   It finds the longest continuous sequence of characters present in both strings.

3. Final Answer:

   The longest sequence of characters that appear contiguously in both strings -> Option C

4. Quick Check:

   Longest Common Substring = continuous match [OK]

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

Common Mistakes:

• Confusing substring with subsequence
• Thinking order doesn't matter
• Counting total common characters instead

2. Which of the following TypeScript function signatures correctly represents a function to find the longest common substring length between two strings s1 and s2?

easy

A. function longestCommonSubstring(s1: string, s2: string): number

B. function longestCommonSubstring(s1: number[], s2: number[]): string

C. function longestCommonSubstring(s1: string, s2: string): string[]

D. function longestCommonSubstring(s1: string, s2: string): void

Solution

1. Step 1: Identify input types

   The inputs are two strings, so parameters should be string.

2. Step 2: Identify output type

   The function returns the length of the longest common substring, which is a number.

3. Final Answer:

   function longestCommonSubstring(s1: string, s2: string): number -> Option A

4. Quick Check:

   Input strings, output number length [OK]

Hint: Match input/output types to problem description [OK]

Common Mistakes:

• Using arrays instead of strings as input
• Returning string or array instead of number
• Using void return type mistakenly

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

function longestCommonSubstring(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  let maxLen = 0;
  const dp: number[][] = Array(m + 1).fill(0).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;
        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: Compare characters of 'abcde' and 'abfde'

   Matching continuous substrings are 'ab' at start and 'de' at end, both length 2.

2. Step 2: Find longest continuous match

   Longest common substring length is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Longest common substring length = 2 [OK]

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

Common Mistakes:

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

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

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

medium

A. Loop indices should start from 0 instead of 1

B. dp array is initialized with wrong size causing index errors

C. maxLen is not updated inside the loop

D. Comparison uses wrong characters from strings

Solution

1. Step 1: Check dp array initialization

   dp is created with size m x n but accessed with indices up to m and n (1-based), causing out-of-bound errors.

2. Step 2: Correct dp size

   dp should be (m+1) x (n+1) to safely use 1-based indexing in loops.

3. Final Answer:

   dp array is initialized with wrong size causing index errors -> Option B

4. Quick Check:

   dp size must match loop indices [OK]

Hint: Match dp size with loop ranges to avoid index errors [OK]

Common Mistakes:

• Not adding +1 to dp dimensions
• Starting loops at 1 but dp size too small
• Ignoring index out-of-bound runtime errors

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

hard

A. 3

B. 5

C. 6

D. 4

Solution

1. Step 1: Identify common substrings

   Common substrings include 'abx' and 'abxa'. 'abxa' is length 4 and appears in both strings.

2. Step 2: Confirm longest substring length

   No longer continuous substring than length 4 exists in both strings.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Longest common substring length = 4 [OK]

Hint: Look for longest continuous matching sequence visually [OK]

Common Mistakes:

• Counting non-continuous matches
• Choosing shorter common substrings
• Confusing substring with subsequence