Longest Common Substring in DSA Javascript

Mental Model

Find the longest sequence of characters that appears in both strings without skipping any characters.

Analogy: Imagine two friends reading two different books and trying to find the longest exact sentence that appears in both books without any missing words.

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

Dry Run Walkthrough

Input: string1: 'abcde', string2: 'abfde'

Goal: Find the longest substring that appears in both strings exactly and continuously

Step 1: Compare 'a' from string1 with 'a' from string2, they match, start substring length 1

Match found: 'a' -> length 1

Why: Start tracking common substring length when characters match

Step 2: Compare 'b' from string1 with 'b' from string2, they match, substring length becomes 2

Match found: 'ab' -> length 2

Why: Extend substring length as characters continue to match

Step 3: Compare 'c' from string1 with 'f' from string2, no match, reset substring length to 0

No match at 'c' vs 'f', reset length to 0

Why: Substring must be continuous, so reset when characters differ

Step 4: Compare 'd' from string1 with 'd' from string2, match, substring length 1

Match found: 'd' -> length 1

Why: Start new substring length count after reset

Step 5: Compare 'e' from string1 with 'e' from string2, match, substring length 2

Match found: 'de' -> length 2

Why: Extend substring length as characters continue to match

Result:

Longest common substring is 'ab' or 'de' with length 2

Annotated Code

DSA Javascript

class LongestCommonSubstring {
  static find(str1, str2) {
    const m = str1.length;
    const n = str2.length;
    let maxLen = 0;
    let endingIndex = 0;
    // Create 2D array filled with 0
    const dp = 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 (str1[i - 1] === str2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1] + 1; // extend substring length
          if (dp[i][j] > maxLen) {
            maxLen = dp[i][j]; // update max length
            endingIndex = i - 1; // update ending index of substring in str1
          }
        } else {
          dp[i][j] = 0; // reset length when chars differ
        }
      }
    }

    const longestSubstring = str1.substring(endingIndex - maxLen + 1, endingIndex + 1);
    return { longestSubstring, length: maxLen };
  }
}

// Driver code
const str1 = 'abcde';
const str2 = 'abfde';
const result = LongestCommonSubstring.find(str1, str2);
console.log(`Longest common substring: '${result.longestSubstring}' with length ${result.length}`);

if (str1[i - 1] === str2[j - 1]) {

Check if current characters match to extend substring length

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

Extend length of common substring by 1 from previous diagonal

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

Update max length and ending index if current substring is longer

dp[i][j] = 0;

Reset length to 0 when characters do not match

Output

Longest common substring: 'ab' with length 2

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 use a 2D array to store lengths of common substrings ending at each pair of indices

vs Alternative: Naive approach checks all substrings and is O(m^2*n^2), dynamic programming reduces it to O(m*n)

Edge Cases

One or both strings empty

Returns empty substring with length 0

DSA Javascript

const m = str1.length; const n = str2.length;

No common substring

Returns empty substring with length 0

DSA Javascript

dp[i][j] = 0;

Strings are identical

Returns the entire string as longest common substring

DSA Javascript

if (dp[i][j] > maxLen) { maxLen = dp[i][j]; endingIndex = i - 1; }

When to Use This Pattern

When you need to find the longest exact continuous match between two strings, use the Longest Common Substring pattern with dynamic programming to efficiently track matching sequences.

Common Mistakes

Mistake: Confusing longest common substring with longest common subsequence which allows skipping characters
Fix: Remember substring must be continuous; reset length to zero when characters differ

Mistake: Not updating the max length and ending index correctly
Fix: Update maxLen and endingIndex inside the condition when dp[i][j] exceeds current maxLen

Summary

Finds the longest continuous sequence of characters common to both strings.

Use when you need the longest exact matching substring between two strings.

Track substring lengths with a 2D table and reset when characters differ to ensure continuity.

Practice

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

easy

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

B. The longest sequence of characters that appear anywhere in both strings, not necessarily consecutively

C. The total number of common characters between two strings

D. The longest sequence of characters that appear consecutively in both strings

Solution

1. Step 1: Understand the problem definition

   The Longest Common Substring problem looks for the longest continuous sequence of characters shared by both strings.

2. Step 2: Differentiate from similar problems

   Unlike Longest Common Subsequence, the substring must be consecutive characters, not scattered.

3. Final Answer:

   The longest sequence of characters that appear consecutively in both strings -> Option D

4. Quick Check:

   Longest Common Substring = consecutive matching characters [OK]

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

Common Mistakes:

• Confusing substring with subsequence
• Thinking order does not matter
• Ignoring continuity requirement

2. Which of the following JavaScript code snippets correctly initializes a 2D array for dynamic programming in Longest Common Substring?

easy

A. const dp = Array(m + 1).fill(Array(n + 1).fill(0));

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

C. const dp = new Array(m + 1).fill(new Array(n + 1).fill(0));

D. const dp = Array(m + 1).map(Array(n + 1).fill(0));

Solution

1. Step 1: Understand 2D array initialization in JavaScript

   Using Array.from with a mapping function creates independent inner arrays, avoiding shared references.

2. Step 2: Analyze each option

   Options B and C use fill with arrays, causing all rows to reference the same inner array. const dp = Array(m + 1).map(Array(n + 1).fill(0)); passes Array(n + 1).fill(0) directly to map, which expects a function and causes TypeError.

3. Final Answer:

   const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0)); -> Option B

4. Quick Check:

   Use Array.from with function for independent rows [OK]

Hint: Use Array.from with function to avoid shared inner arrays [OK]

Common Mistakes:

• Using fill with arrays causing shared references
• Using map on uninitialized arrays
• Not initializing inner arrays properly

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

function longestCommonSubstring(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));
  let maxLen = 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: Trace matching characters between 'abcde' and 'abfde'

   Matching substrings are 'ab' at start and 'de' at end. Both have length 2.

2. Step 2: Identify longest common substring length

   Longest common substring length is 2, from either 'ab' or 'de'.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Longest common substring length = 2 [OK]

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

Common Mistakes:

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

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

function lcsLength(s1, s2) {
  const m = s1.length, n = s2.length;
  const dp = Array(m + 1).fill(Array(n + 1).fill(0));
  let maxLen = 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. dp array rows share the same inner array causing incorrect updates

B. Loop indices start from 1 instead of 0 causing index errors

C. The maxLen variable is not updated inside the loop

D. The function returns dp[m][n] instead of maxLen

Solution

1. Step 1: Analyze dp array initialization

   Using fill with an array causes all rows to reference the same inner array, so updates affect all rows.

2. Step 2: Understand impact on dp updates

   Because rows share the same array, dp[i][j] updates overwrite other rows, corrupting the dp table and results.

3. Final Answer:

   dp array rows share the same inner array causing incorrect updates -> Option A

4. Quick Check:

   Shared inner arrays cause dp corruption [OK]

Hint: Avoid fill with arrays; use Array.from with function [OK]

Common Mistakes:

• Using fill for 2D arrays causing shared references
• Ignoring dp table corruption
• Misunderstanding loop indices

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

hard

A. 'xab', length 3

B. 'abx', length 3

C. 'abxa', length 4

D. 'abc', length 3

Solution

1. Step 1: Identify common substrings between s1 and s2

   Check substrings of s1 in s2: 'xab' appears, 'abx' appears, 'abxa' appears in s2 starting at index 4.

2. Step 2: Find the longest continuous match

   'abxa' is length 4 and appears in both strings continuously, longer than other matches.

3. Final Answer:

   'abxa', length 4 -> Option C

4. Quick Check:

   Longest common substring = 'abxa' length 4 [OK]

Hint: Check all continuous matches, pick longest [OK]

Common Mistakes:

• Choosing shorter substrings ignoring longer matches
• Confusing substring with subsequence
• Missing overlapping matches