Longest Common Substring in DSA Typescript - Time & Space Complexity

Time Complexity: Longest Common Substring

O(m x n)

Understanding Time Complexity

We want to understand how the time needed to find the longest common substring between two strings grows as the strings get longer.

How does the work increase when the input strings become bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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;
        maxLen = Math.max(maxLen, dp[i][j]);
      }
    }
  }
  return maxLen;
}
    

This code finds the length of the longest substring that appears in both input strings by using a table to store matching lengths.

Identify Repeating Operations

• Primary operation: Nested loops comparing characters of both strings and updating the table.
• How many times: The outer loop runs m times, and for each, the inner loop runs n times, so total m x n times.

How Execution Grows With Input

As the lengths of the two strings grow, the number of comparisons grows by multiplying their lengths.

Input Size (m and n)	Approx. Operations
10 and 10	100
100 and 100	10,000
1000 and 1000	1,000,000

Pattern observation: Doubling the length of both strings roughly quadruples the work because the loops multiply.

Final Time Complexity

Time Complexity: O(m x n)

This means the time needed grows proportionally to the product of the lengths of the two strings.

Common Mistake

[X] Wrong: "The algorithm only depends on the length of one string, so it is O(n)."

[OK] Correct: The algorithm compares every character of the first string with every character of the second, so both lengths matter and multiply.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming solutions scale and why nested loops are common in string comparison problems.

Self-Check

"What if we only needed to find the longest common prefix instead of substring? How would the time complexity change?"

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