Longest Common Substring in DSA Javascript - Build from Scratch

Longest Common Substring

📖 Scenario: You are working on a text comparison tool that helps users find the longest common substring between two words. This is useful in spell checkers, plagiarism detectors, and DNA sequence analysis.

🎯 Goal: Build a program that finds the longest common substring between two given strings using dynamic programming.

📋 What You'll Learn

Create two string variables with exact values

Create a 2D array to store substring lengths

Implement nested loops to fill the 2D array based on matching characters

Track the maximum length and ending index of the longest common substring

Extract and print the longest common substring

💡 Why This Matters

🌍 Real World

Finding longest common substrings is useful in text editors, DNA sequence analysis, and plagiarism detection.

💼 Career

Understanding dynamic programming and string manipulation is valuable for software development and data analysis roles.

1

Create the input strings

Create two string variables called str1 and str2 with the exact values "ABABC" and "BABCA" respectively.

DSA Javascript

# Your code here

Hint

Use const to declare the strings exactly as shown.

2

Initialize the 2D array and helper variables

Create a 2D array called dp with dimensions str1.length + 1 by str2.length + 1, filled with zeros. Also create variables maxLength and endIndex initialized to 0.

DSA Javascript

const str1 = "ABABC";
const str2 = "BABCA";
// Your code here

Hint

Use Array(...).fill(null).map(...) to create the 2D array filled with zeros.

3

Fill the 2D array to find longest common substring

Use nested for loops with variables i from 1 to str1.length and j from 1 to str2.length. Inside, if str1[i - 1] equals str2[j - 1], set dp[i][j] to dp[i - 1][j - 1] + 1. If dp[i][j] is greater than maxLength, update maxLength to dp[i][j] and endIndex to i.

DSA Javascript

const str1 = "ABABC";
const str2 = "BABCA";

const dp = Array(str1.length + 1).fill(null).map(() => Array(str2.length + 1).fill(0));
let maxLength = 0;
let endIndex = 0;

// Your code here

Hint

Remember to start loops from 1 because dp array has extra row and column for zeros.

4

Extract and print the longest common substring

Create a variable longestSubstring by slicing str1 from endIndex - maxLength to endIndex. Then print longestSubstring using console.log.

DSA Javascript

const str1 = "ABABC";
const str2 = "BABCA";

const dp = Array(str1.length + 1).fill(null).map(() => Array(str2.length + 1).fill(0));
let maxLength = 0;
let endIndex = 0;

for (let i = 1; i  maxLength) {
                maxLength = dp[i][j];
                endIndex = i;
            }
        }
    }
}

// Your code here

Hint

Use str1.slice(endIndex - maxLength, endIndex) to get the substring.

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