Longest Common Prefix in DSA Javascript - Build from Scratch

Longest Common Prefix

📖 Scenario: Imagine you work in a company that manages a list of product codes. You want to find the longest common starting part (prefix) shared by all product codes to group them easily.

🎯 Goal: Build a program that finds the longest common prefix string among an array of product codes.

📋 What You'll Learn

Create an array called productCodes with the exact values: ['flower', 'flow', 'flight']

Create a variable called prefix and set it to an empty string ''

Use a for loop with variable i to iterate over characters of the first product code

Use a nested for loop with variable j to check the character at position i in all product codes

Stop checking when characters do not match or end of any product code is reached

Print the final value of prefix

💡 Why This Matters

🌍 Real World

Finding common prefixes helps group similar product codes, usernames, or file paths to organize data efficiently.

💼 Career

This skill is useful for software developers working on search engines, autocomplete features, or data grouping algorithms.

1

Create the product codes array

Create an array called productCodes with these exact values: ['flower', 'flow', 'flight']

DSA Javascript

# Create the array productCodes with the given values
# Your code here

Hint

Use const productCodes = ['flower', 'flow', 'flight']; to create the array.

2

Create the prefix variable

Create a variable called prefix and set it to an empty string ''

DSA Javascript

const productCodes = ['flower', 'flow', 'flight'];
// Create prefix variable as empty string
# Your code here

Hint

Use let prefix = ''; to create an empty string variable.

3

Find the longest common prefix

Use a for loop with variable i to iterate over characters of the first product code productCodes[0]. Inside it, use a for loop with variable j to check the character at position i in all product codes. Stop checking when characters do not match or end of any product code is reached. If all match, add the character to prefix.

DSA Javascript

const productCodes = ['flower', 'flow', 'flight'];
let prefix = '';
// Use nested loops to find longest common prefix
# Your code here

Hint

Use two loops: outer loop over characters of first string, inner loop over all strings to compare characters.

4

Print the longest common prefix

Write console.log(prefix) to print the longest common prefix found.

DSA Javascript

const productCodes = ['flower', 'flow', 'flight'];
let prefix = '';
for (let i = 0; i = productCodes[j].length || productCodes[j][i] !== char) {
            i = productCodes[0].length; // break outer loop
            break;
        }
    }
    if (i < productCodes[0].length) {
        prefix += char;
    }
}
// Print the prefix
# Your code here

Hint

Use console.log(prefix); to show the result.

Practice

1. What does the Longest Common Prefix (LCP) problem ask you to find given an array of strings?

easy

A. The longest substring common to any two strings

B. The longest starting substring common to all strings

C. The longest ending substring common to all strings

D. The shortest substring unique to each string

Solution

1. Step 1: Understand the problem definition

   The Longest Common Prefix means the longest substring at the start of all strings that is the same.

2. Step 2: Compare options with definition

   Only The longest starting substring common to all strings matches this definition exactly.

3. Final Answer:

   The longest starting substring common to all strings -> Option B

4. Quick Check:

   Longest Common Prefix = longest starting substring [OK]

Hint: Focus on the start of strings for common prefix [OK]

Common Mistakes:

• Confusing prefix with suffix
• Looking for substring anywhere, not just start
• Thinking about unique substrings

2. Which of the following is the correct JavaScript syntax to start a function named longestCommonPrefix that takes an array strs as input?

easy

A. function: longestCommonPrefix(strs) { }

B. func longestCommonPrefix(strs) { }

C. function longestCommonPrefix(strs) { }

D. def longestCommonPrefix(strs):

Solution

1. Step 1: Recall JavaScript function syntax

   JavaScript functions start with the keyword 'function' followed by name and parentheses.

2. Step 2: Check each option

   function longestCommonPrefix(strs) { } matches JavaScript syntax. Options B and C are from other languages. function: longestCommonPrefix(strs) { } is invalid syntax.

3. Final Answer:

   function longestCommonPrefix(strs) { } -> Option C

4. Quick Check:

   JS function syntax = function name(params) { } [OK]

Hint: JS functions start with 'function' keyword [OK]

Common Mistakes:

• Using Python or other language syntax
• Adding colon after function name
• Using 'func' instead of 'function'

3. What will be the output of the following JavaScript code?

function longestCommonPrefix(strs) {
  if (strs.length === 0) return "";
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.substring(0, prefix.length - 1);
      if (prefix === "") return "";
    }
  }
  return prefix;
}

console.log(longestCommonPrefix(["flower", "flow", "flight"]));

medium

A. "fl"

B. "flow"

C. "f"

D. "flower"

Solution

1. Step 1: Initialize prefix and loop through strings

   Prefix starts as "flower". Check "flow": "flower" is not prefix, shorten to "flowe", then "flow", which matches start of "flow".

2. Step 2: Check next string "flight"

   "flow" is not prefix of "flight", shorten to "flo", no match; then "fl", which matches start of "flight".

3. Final Answer:

   "fl" -> Option A

4. Quick Check:

   Common prefix of flower, flow, flight = "fl" [OK]

Hint: Shrink prefix until it matches all strings start [OK]

Common Mistakes:

• Returning first string as prefix
• Not shrinking prefix correctly
• Confusing substring with suffix

4. Find the bug in this JavaScript function for Longest Common Prefix:

function longestCommonPrefix(strs) {
  if (!strs.length) return "";
  let prefix = strs[0];
  for (let i = 1; i <= strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.substring(0, prefix.length - 1);
      if (prefix === "") return "";
    }
  }
  return prefix;
}

medium

A. The for loop condition should be i < strs.length, not i <= strs.length

B. The prefix should be initialized as an empty string

C. The while loop condition should use includes() instead of indexOf()

D. The function should return prefix inside the for loop

Solution

1. Step 1: Check for loop bounds

   The for loop uses i <= strs.length, which causes out-of-bounds access at last iteration.

2. Step 2: Correct loop condition

   Changing to i < strs.length prevents accessing undefined strs[i].

3. Final Answer:

   The for loop condition should be i < strs.length, not i <= strs.length -> Option A

4. Quick Check:

   Loop index must be less than array length [OK]

Hint: Use < not <= for array indices [OK]

Common Mistakes:

• Off-by-one error in loop
• Wrong initialization of prefix
• Misusing string methods

5. Given an array of strings, how would you modify the Longest Common Prefix algorithm to handle the case where some strings are empty or the array is empty, ensuring no errors and correct output?

hard

A. Throw an error if any string is empty

B. Ignore empty strings and find prefix among non-empty strings only

C. Replace empty strings with the first string in the array before processing

D. Return an empty string immediately if the array is empty or any string is empty

Solution

1. Step 1: Check for empty array or empty strings

   If the array is empty or any string is empty, the longest common prefix must be empty string.

2. Step 2: Return empty string early

   Returning "" immediately avoids errors and matches expected output.

3. Final Answer:

   Return an empty string immediately if the array is empty or any string is empty -> Option D

4. Quick Check:

   Empty input means empty prefix [OK]

Hint: Check for empty inputs first [OK]

Common Mistakes:

• Not handling empty strings causing errors
• Ignoring empty strings and causing wrong prefix
• Throwing errors instead of returning empty string