Why Longest Common Substring in DSA Javascript?

The Big Idea

Discover how computers find the longest matching piece between two texts in a blink!

The Scenario

Imagine you have two long texts and you want to find the longest exact matching part between them. Doing this by reading and comparing every possible part by hand would be like searching for a needle in a haystack.

The Problem

Manually checking every possible substring is very slow and tiring. It's easy to miss matches or make mistakes, especially when the texts are long. This approach wastes time and causes frustration.

The Solution

The Longest Common Substring algorithm quickly finds the longest matching part between two texts by comparing them smartly using a table. It saves time and avoids errors by automating the search.

Before vs After

✗ Before

const text1 = 'hello';
const text2 = 'yellow';
// Manually check all substrings one by one
// Very slow and complex

✓ After

function longestCommonSubstring(str1, str2) {
  // Use a table to find longest matching substring
  // Returns the longest common substring
}

What It Enables

This lets you quickly find the longest exact matching part between two strings, enabling tasks like spell checking, DNA matching, or plagiarism detection.

Real Life Example

When you type a word and your phone suggests corrections, it uses longest common substring ideas to find the closest matching words from its dictionary.

Key Takeaways

Manual substring search is slow and error-prone.

Longest Common Substring algorithm automates and speeds up the search.

It helps in many real-world tasks like text comparison and error correction.

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