Longest Common Substring in DSA Javascript - Deep Dive

Overview - Longest Common Substring

What is it?

The Longest Common Substring problem finds the longest sequence of characters that appears in the same order and contiguously in two given strings. Unlike the Longest Common Subsequence, the characters must be next to each other without gaps. This helps identify shared parts between strings exactly as they appear.

Why it matters

Finding the longest common substring helps in many real-world tasks like detecting plagiarism, DNA sequence analysis, and file comparison. Without this concept, computers would struggle to find exact matching parts efficiently, making tasks like text search and data comparison slow and inaccurate.

Where it fits

Before learning this, you should understand basic strings and arrays. After mastering this, you can explore related problems like Longest Common Subsequence and advanced string matching algorithms.

Mental Model

Core Idea

The longest common substring is the longest continuous piece shared exactly between two strings.

Think of it like...

It's like finding the longest matching piece of tape stuck on two different rolls without any breaks in the tape.

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

Matching substrings:
  c d e
Longest common substring: c d e

Build-Up - 7 Steps

1

Foundation

Understanding substrings and continuity

Concept: Learn what substrings are and why continuity matters.

A substring is a part of a string made by taking consecutive characters. For example, in 'hello', 'ell' is a substring but 'eol' is not because the letters are not next to each other. Continuity means the characters appear one after another without skipping.

Result

You can identify substrings and understand that only continuous sequences count.

Understanding continuity is key because the problem only cares about uninterrupted matching parts.

2

Foundation

Comparing two strings character by character

Concept: Learn how to check characters from two strings to find matches.

To find common parts, compare each character of the first string with each character of the second string. When characters match, check if the next characters also match to form a substring.

Result

You can spot where substrings start and how long they continue.

Knowing how to compare characters step-by-step lays the groundwork for building the solution.

3

Intermediate

Using a 2D table to track matches

🤔Before reading on: do you think we can track substring lengths using a table or just by checking characters directly? Commit to your answer.

Concept: Introduce a table (matrix) to store lengths of matching substrings ending at each pair of positions.

Create a 2D array where rows represent characters of the first string and columns represent characters of the second string. Each cell stores the length of the longest common substring ending at those positions. If characters match, add 1 to the diagonal cell's value; otherwise, set to 0.

Result

You get a matrix showing lengths of matching substrings at every position, making it easy to find the longest one.

Using a table transforms the problem into a clear, step-by-step process that computers can handle efficiently.

4

Intermediate

Tracking the maximum substring length and position

🤔Before reading on: do you think we should keep track of the longest substring length as we fill the table, or find it after filling? Commit to your answer.

Concept: Keep updating the maximum length and its position while filling the table to avoid extra passes.

While filling the 2D table, whenever you find a cell with a value greater than the current maximum, update the maximum length and record the position. This helps identify where the longest substring ends.

Result

You know the length and ending position of the longest common substring immediately after processing.

Tracking max length on the fly saves time and simplifies extracting the result.

5

Intermediate

Extracting the longest common substring from indices

Concept: Use the recorded position and length to get the substring from the original string.

Once you have the ending index and length, slice the substring from the first string starting at (end index - length + 1) to the end index. This substring is the longest common substring.

Result

You get the actual substring, not just its length.

Knowing how to extract the substring connects the algorithm's numbers back to meaningful text.

6

Advanced

Implementing the solution in JavaScript

🤔Before reading on: do you think the solution needs nested loops or can it be done with a single loop? Commit to your answer.

Concept: Write a complete JavaScript function using nested loops and a 2D array to find the longest common substring.

function longestCommonSubstring(s1, s2) { const m = s1.length; const n = s2.length; const dp = 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; if (dp[i][j] > maxLen) { maxLen = dp[i][j]; endIndex = i - 1; } } else { dp[i][j] = 0; } } } return s1.slice(endIndex - maxLen + 1, endIndex + 1); } // Example usage: console.log(longestCommonSubstring('abcdefg', 'xyzcdefz'));

Result

Output: 'cdef' This is the longest common substring between the two strings.

Seeing the full code helps connect theory to practice and shows how to implement the concept efficiently.

7

Expert

Optimizing space with rolling arrays

🤔Before reading on: do you think we need to keep the entire 2D table in memory, or can we reduce it? Commit to your answer.

Concept: Reduce memory usage by storing only the previous row instead of the full 2D table.

Since each dp[i][j] depends only on dp[i-1][j-1], we can keep just one previous row array and update the current row. This reduces space from O(m*n) to O(n). The logic remains the same but memory is saved.

Result

The algorithm uses less memory but still finds the longest common substring correctly.

Understanding dependencies in dynamic programming allows memory optimization without losing correctness.

Under the Hood

The algorithm uses dynamic programming to build a table where each cell represents the length of the longest common substring ending at those indices. It compares characters and extends matches diagonally in the table. This avoids redundant checks by reusing previous results, making the process efficient.

Why designed this way?

Dynamic programming was chosen because naive checking of all substrings would be very slow (quadratic or worse). The table approach breaks the problem into smaller overlapping subproblems, storing results to avoid repeated work. Alternatives like suffix trees exist but are more complex to implement.

  s2 chars ->
  +---+---+---+---+---+---+---+---+
  |   | x | y | c | d | e | f | z |
  +---+---+---+---+---+---+---+---+
s1|   | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
 c| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
 d| 0 | 0 | 0 | 0 | 2 | 0 | 0 | 0 |
 e| 0 | 0 | 0 | 0 | 0 | 3 | 0 | 0 |
 f| 0 | 0 | 0 | 0 | 0 | 0 | 4 | 0 |

Diagonal increments show substring length growing.

Myth Busters - 3 Common Misconceptions

Quick: Does the longest common substring allow skipping characters in between? Commit to yes or no.

Common Belief: The longest common substring can skip characters as long as the order is maintained.

Reality: No, the substring must be continuous without skipping any characters.

Why it matters: Confusing substring with subsequence leads to wrong algorithms and incorrect results.

Quick: Is the longest common substring always unique? Commit to yes or no.

Common Belief: There is always only one longest common substring between two strings.

Reality: There can be multiple longest common substrings of the same maximum length.

Why it matters: Assuming uniqueness can cause bugs when extracting or reporting results.

Quick: Can we find the longest common substring efficiently without comparing all character pairs? Commit to yes or no.

Common Belief: We can find the longest common substring quickly without checking many character pairs.

Reality: The standard dynamic programming approach requires checking pairs, though advanced structures like suffix trees can optimize this.

Why it matters: Expecting a simple shortcut may lead to inefficient or incorrect solutions.

Expert Zone

1

The dynamic programming table only needs to store lengths of substrings ending at positions, not the substrings themselves, saving memory.

2

When multiple longest substrings exist, the algorithm can be adapted to collect all by tracking positions with max length.

3

Suffix automata or suffix trees can find longest common substrings in linear time but are complex to implement and understand.

When NOT to use

Avoid this approach when working with very large strings where memory is limited; consider suffix trees or suffix arrays instead. Also, if you need longest common subsequence (non-continuous), this method is not suitable.

Production Patterns

Used in plagiarism detection tools to find copied text segments, in bioinformatics to find shared DNA sequences, and in file comparison utilities to highlight exact matching parts.

Connections

Longest Common Subsequence

Related problem with similar dynamic programming approach but allows non-continuous matches.

Understanding longest common substring clarifies the stricter continuity requirement compared to subsequence, helping grasp both concepts deeply.

Suffix Trees

Advanced data structure that can find longest common substrings more efficiently.

Knowing the dynamic programming solution prepares you to appreciate the power and complexity of suffix trees.

Genetics and DNA Sequencing

Longest common substring algorithms help find shared sequences in DNA strands.

Seeing this algorithm applied in biology shows how computer science solves real-world problems in other fields.

Common Pitfalls

#1 Confusing longest common substring with longest common subsequence.

Wrong approach:

function longestCommonSubstring(s1, s2) {
// Incorrectly allowing non-continuous matches
// This is actually longest common subsequence logic
const m = s1.length, n = s2.length;
const dp = Array.from({ length: m + 1 }, () => 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;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}

Correct approach:

function longestCommonSubstring(s1, s2) {
const m = s1.length;
const n = s2.length;
const dp = 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;
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
endIndex = i - 1;
}
} else {
dp[i][j] = 0;
}
}
}
return s1.slice(endIndex - maxLen + 1, endIndex + 1);
}

Root cause:

Misunderstanding the difference between substring (continuous) and subsequence (non-continuous) leads to wrong algorithm choice.

#2 Not resetting dp cell to zero when characters don't match.

Wrong approach:

if (s1[i - 1] === s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = dp[i - 1][j - 1]; // wrong: should be zero
}

Correct approach:

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

Root cause:

Failing to reset breaks the continuity rule, causing incorrect substring lengths.

#3 Extracting substring using wrong indices after finding max length.

Wrong approach:

return s1.slice(endIndex, endIndex + maxLen); // wrong start index

Correct approach:

return s1.slice(endIndex - maxLen + 1, endIndex + 1);

Root cause:

Off-by-one errors in indexing cause wrong substring extraction.

Key Takeaways

The longest common substring is the longest continuous matching part between two strings.

Dynamic programming uses a table to track substring lengths ending at each position, enabling efficient computation.

Tracking the maximum length and position during table filling helps extract the substring without extra passes.

Memory can be optimized by storing only one row of the table at a time due to dependency on previous row.

Understanding the difference between substring and subsequence is crucial to applying the correct algorithm.

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