Longest Common Prefix in DSA Javascript

Mental Model

Find the longest starting part that all words share. We compare letters from the start until they differ.

Analogy: Imagine several friends starting a race together. The longest common prefix is like the longest stretch of road they all run side by side before some take different turns.

words: [flower, flow, flight]
indexes:  0123456789
prefix:  ↑↑

Dry Run Walkthrough

Input: words: ["flower", "flow", "flight"]

Goal: Find the longest prefix that all words start with

Step 1: Start with prefix as the first word 'flower'

prefix = 'flower'
words = ['flower', 'flow', 'flight']

Why: We use the first word as a starting guess for the prefix

Step 2: Compare prefix 'flower' with second word 'flow', shorten prefix to match

prefix = 'flow'
words = ['flower', 'flow', 'flight']

Why: We cut prefix down to the common start of 'flower' and 'flow'

Step 3: Compare prefix 'flow' with third word 'flight', shorten prefix further

prefix = 'fl'
words = ['flower', 'flow', 'flight']

Why: We cut prefix down to the common start of 'flow' and 'flight'

Step 4: No more words to compare, return prefix 'fl'

prefix = 'fl'

Why: All words share 'fl' at the start

Result:

prefix = 'fl'

Annotated Code

DSA Javascript

class Solution {
  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;
  }
}

const solution = new Solution();
const input = ["flower", "flow", "flight"];
console.log(solution.longestCommonPrefix(input));

if (strs.length === 0) return "";

handle empty input list by returning empty prefix

let prefix = strs[0];

start prefix as first word to compare with others

for (let i = 1; i < strs.length; i++) {

iterate over each word after the first

while (strs[i].indexOf(prefix) !== 0) {

reduce prefix until it matches the start of current word

prefix = prefix.substring(0, prefix.length - 1);

shorten prefix by removing last character

if (prefix === "") return "";

if prefix is empty, no common prefix exists

return prefix;

return the longest common prefix found

Output

fl

Complexity Analysis

Time: O(S) because we compare characters of all strings where S is the sum of all characters

Space: O(1) because we only store the prefix string and no extra data structures

vs Alternative: Compared to checking character by character for all strings simultaneously, this approach reduces repeated comparisons by shrinking prefix early

Edge Cases

empty list

returns empty string immediately

DSA Javascript

if (strs.length === 0) return "";

list with one word

returns that word as prefix

DSA Javascript

let prefix = strs[0];

no common prefix

prefix shrinks to empty string and returns empty

DSA Javascript

if (prefix === "") return "";

When to Use This Pattern

When asked to find the longest starting substring common to all strings, use the longest common prefix pattern by iteratively shrinking a candidate prefix.

Common Mistakes

Mistake: Comparing characters one by one for all strings without shrinking prefix early
Fix: Start with first word as prefix and shrink it by checking whole prefix against each word

Mistake: Not handling empty input list causing errors
Fix: Add a check to return empty string if input list is empty

Summary

Finds the longest starting substring common to all strings in a list.

Use when you need to find shared beginnings among multiple words or strings.

Start with the first word as prefix and shrink it until it matches all words.

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