Longest Common Substring in DSA Typescript

Mental Model

Find the longest sequence of characters that appears exactly the same and continuously in both strings.

Analogy: Imagine two friends comparing their favorite songs to find the longest exact part of the melody they both like without breaks.

String1: a b c d e f g
String2: x y c d e z

We look for the longest continuous matching part: c d e

Dry Run Walkthrough

Input: string1: "abcde", string2: "abfde"

Goal: Find the longest continuous substring common to both strings

Step 1: Initialize a 2D array dp with zeros for lengths of substrings

dp matrix (rows for string1, cols for string2) all zeros

Why: We need a table to store lengths of matching substrings ending at each pair of indices

Step 2: Compare characters at string1[0] and string2[0] ('a' and 'a'), they match, set dp[1][1] = 1

dp[1][1] = 1, rest zeros

Why: Matching characters start a substring of length 1

Step 3: Compare string1[1] and string2[1] ('b' and 'b'), match, dp[2][2] = dp[1][1] + 1 = 2

dp[2][2] = 2, dp[1][1] = 1, others zero

Why: Extend previous matching substring by 1

Step 4: Compare string1[2] and string2[2] ('c' and 'f'), no match, dp[3][3] = 0

dp[3][3] = 0

Why: Mismatch breaks the substring

Step 5: Compare string1[4] and string2[4] ('e' and 'e'), match, dp[5][5] = dp[4][4] + 1 = 1

dp[5][5] = 1

Why: Start new matching substring of length 1

Result:

Longest common substring length is 2 with substring "ab"

Annotated Code

DSA Typescript

class LongestCommonSubstring {
  static find(s1: string, s2: string): {length: number; substring: string} {
    const m = s1.length;
    const n = s2.length;
    const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
    let maxLen = 0;
    let endIndex = 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; // extend matching substring
          if (dp[i][j] > maxLen) {
            maxLen = dp[i][j]; // update max length
            endIndex = i; // track end index of substring in s1
          }
        } else {
          dp[i][j] = 0; // reset on mismatch
        }
      }
    }

    const substring = s1.substring(endIndex - maxLen, endIndex);
    return { length: maxLen, substring };
  }
}

// Driver code
const s1 = "abcde";
const s2 = "abfde";
const result = LongestCommonSubstring.find(s1, s2);
console.log(`Length: ${result.length}`);
console.log(`Substring: ${result.substring}`);

if (s1[i - 1] === s2[j - 1]) {

Check if characters match to extend substring

dp[i][j] = dp[i - 1][j - 1] + 1;

Extend length of matching substring by 1

if (dp[i][j] > maxLen) {

Update max length and end index if longer substring found

dp[i][j] = 0;

Reset length on mismatch

Output

Length: 2

Substring: ab

Complexity Analysis

Time: O(m*n) because we compare each character of first string with each character of second string once

Space: O(m*n) because we store lengths of substrings in a 2D table of size m+1 by n+1

vs Alternative: Naive approach checks all substrings and is O(m^2*n^2), so DP is much faster

Edge Cases

One or both strings empty

Returns length 0 and empty substring

DSA Typescript

const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

No common substring

Returns length 0 and empty substring

DSA Typescript

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

Strings are identical

Returns full string length and string

DSA Typescript

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

When to Use This Pattern

When asked to find the longest continuous matching part between two strings, use the Longest Common Substring pattern with dynamic programming to efficiently track matching lengths.

Common Mistakes

Mistake: Confusing longest common substring with longest common subsequence (which allows gaps)
Fix: Remember substring requires continuous characters; use DP that resets on mismatch

Mistake: Not resetting dp[i][j] to zero on mismatch, causing incorrect length counts
Fix: Explicitly set dp[i][j] = 0 when characters don't match

Summary

Finds the longest continuous substring common to two strings.

Use when you need the longest exact matching sequence without breaks.

Track lengths of matching substrings ending at each position and reset on mismatch.

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