Longest Common Prefix in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Longest Common Prefix (LCP) in a list of strings?

The Longest Common Prefix is the longest starting substring that is common to all strings in the list. For example, for ["flower", "flow", "flight"], the LCP is "fl".

beginner

How can you find the Longest Common Prefix by comparing characters?

Compare characters of the first string with the same position characters of all other strings. Stop when a mismatch or end of any string is found. The matched characters form the Longest Common Prefix.

intermediate

What is the time complexity of the straightforward Longest Common Prefix approach?

The time complexity is O(S), where S is the sum of all characters in all strings. This is because in the worst case, all characters of all strings are compared.

intermediate

Why is it helpful to use the shortest string in the list when finding the Longest Common Prefix?

Because the Longest Common Prefix cannot be longer than the shortest string. Using it limits the maximum prefix length to check, improving efficiency.

intermediate

What is a simple JavaScript method to find the Longest Common Prefix using string slicing?

Start with the first string as prefix. For each other string, reduce the prefix length by slicing until the prefix matches the start of that string. The remaining prefix is the Longest Common Prefix.

What does the Longest Common Prefix represent in a list of strings?

A The shortest string in the list

B The longest substring common at the end of all strings

C The longest substring common anywhere in all strings

D The longest substring common at the start of all strings

The Longest Common Prefix is the longest substring that appears at the beginning of all strings.

If the list is ["dog", "racecar", "car"], what is the Longest Common Prefix?

A "d"

B "" (empty string)

C "car"

D "do"

There is no common starting substring among all strings, so the Longest Common Prefix is an empty string.

Which of these is an efficient first step to find the Longest Common Prefix?

A Sort the strings alphabetically

B Reverse all strings

C Find the shortest string in the list

D Concatenate all strings

Finding the shortest string helps limit the maximum prefix length to check.

What happens when a mismatch is found while comparing characters for LCP?

A Stop and return the prefix found so far

B Ignore the mismatch and skip to next string

C Restart comparison from the first string

D Continue comparing next characters

When a mismatch occurs, the current matched prefix is the Longest Common Prefix.

What is the worst-case time complexity of the Longest Common Prefix algorithm?

A O(S), where S is total characters in all strings

B O(1)

C O(N)

D O(N^2)

In the worst case, all characters of all strings are compared, so complexity is O(S).

Explain how to find the Longest Common Prefix in a list of strings using character comparison.

Think about checking each character position across all strings.

Describe why the shortest string in the list is important when finding the Longest Common Prefix.

Consider the maximum possible prefix length.

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