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?"