Longest Common Prefix in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Common Prefix Function

What is the output of the following TypeScript code that finds the longest common prefix among strings?

DSA Typescript

function longestCommonPrefix(strs: string[]): string {
  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"]));

A "flow"

B "fl"

C "f"

D "flight"

💡 Hint

Check the common starting letters of all strings.

The function starts with the first string as the prefix and reduces it until all strings start with it. Here, "fl" is the longest prefix common to all.

❓ Predict Output

intermediate

Longest Common Prefix with No Common Prefix

What does the following code print when there is no common prefix?

DSA Typescript

function longestCommonPrefix(strs: string[]): string {
  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(["dog", "racecar", "car"]));

A "dog"

B "d"

C "car"

D ""

💡 Hint

If no letters match at the start, the prefix is empty.

None of the strings share a common starting letter, so the longest common prefix is an empty string.

🔧 Debug

advanced

Identify the Error in Longest Common Prefix Implementation

What error will this TypeScript code produce when run?

DSA Typescript

function longestCommonPrefix(strs: string[]): string {
  if (strs.length === 0) return "";
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (strs[i].startsWith(prefix) === false) {
      prefix = prefix.slice(0, prefix.length - 1);
      if (prefix === "") return "";
    }
  }
  return prefix;
}

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

A Returns "" (empty string)

B Returns "low"

C Returns "fl"

D Runtime error

💡 Hint

Check how prefix is shortened inside the loop.

The code incorrectly removes the first character of prefix instead of the last, so it never finds the correct prefix and ends up empty.

🧠 Conceptual

advanced

Longest Common Prefix Algorithm Complexity

What is the time complexity of the standard longest common prefix algorithm that compares characters one by one among all strings?

A O(N * log M) where N is number of strings and M is length of shortest string

B O(N + M) where N is number of strings and M is length of longest string

C O(N * M) where N is number of strings and M is length of shortest string

D O(M^2) where M is length of shortest string

💡 Hint

Consider worst case comparing each character of each string.

The algorithm compares each character of the shortest string with all other strings, leading to O(N * M) complexity.

🚀 Application

expert

Longest Common Prefix with Unicode Characters

Given the following TypeScript code, what is the output when the input strings contain Unicode characters?

DSA Typescript

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

console.log(longestCommonPrefix(["café", "caféteria", "cafè"]));

A "caf"

B "café"

C "cafè"

D ""

💡 Hint

Unicode characters with accents may differ even if visually similar.

The longest common prefix is "caf" because the accented characters differ, so the prefix stops before them.

Practice

1. What does the Longest Common Prefix (LCP) of a list of strings represent?

easy

A. The longest starting substring common to all strings

B. The longest ending substring common to all strings

C. The longest substring found anywhere in all strings

D. The shortest string in the list

Solution

1. Step 1: Understand the prefix concept

   A prefix is a substring at the start of a string.

2. Step 2: Define longest common prefix

   The LCP is the longest substring starting from the beginning that all strings share.

3. Final Answer:

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

4. Quick Check:

   Prefix means start of string = B [OK]

Hint: Focus on the start of strings to find common parts [OK]

Common Mistakes:

• Confusing prefix with suffix
• Looking for substring anywhere, not just start
• Choosing shortest string as prefix

2. Which of the following TypeScript function signatures correctly represents a function to find the longest common prefix of an array of strings?

easy

A. function longestCommonPrefix(strs: string[]): string

B. function longestCommonPrefix(strs: number[]): string

C. function longestCommonPrefix(strs: string): string[]

D. function longestCommonPrefix(strs: string[]): number

Solution

1. Step 1: Identify input type

   The input should be an array of strings, so type is string[].

2. Step 2: Identify output type

   The output is the longest common prefix, a string.

3. Final Answer:

   function longestCommonPrefix(strs: string[]): string -> Option A

4. Quick Check:

   Input array of strings, output string = D [OK]

Hint: Input is string array, output is string prefix [OK]

Common Mistakes:

• Using number[] instead of string[]
• Returning array instead of string
• Passing single string instead of array

3. What is the output of the following TypeScript code?

function longestCommonPrefix(strs: string[]): string {
  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. "flow"

B. "fl"

C. "f"

D. "flight"

Solution

1. Step 1: Initialize prefix and loop through strings

   Start with prefix = "flower". Check "flow": prefix "flower" not prefix of "flow", shorten to "flowe", then "flow", which is prefix of "flow".

2. Step 2: Check next string "flight"

   "flow" not prefix of "flight", shorten to "flo", then "fl", which is prefix of "flight".

3. Final Answer:

   "fl" -> Option B

4. Quick Check:

   Common start is "fl" = A [OK]

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

Common Mistakes:

• Returning first string without checking others
• Not shortening prefix correctly
• Confusing substring indices

4. Identify the bug in this TypeScript function for longest common prefix:

function longestCommonPrefix(strs: string[]): string {
  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;
}

medium

A. Use prefix.includes() instead of indexOf()

B. Prefix should be initialized as empty string

C. Loop condition should be i < strs.length, not i <= strs.length

D. Return type should be string[] instead of string

Solution

1. Step 1: Check loop boundary

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

2. Step 2: Correct loop condition

   Change to i < strs.length to avoid accessing undefined element.

3. Final Answer:

   Loop condition should be i < strs.length, not i <= strs.length -> Option C

4. Quick Check:

   Array index out of bounds = C [OK]

Hint: Use < not <= for zero-based array loops [OK]

Common Mistakes:

• Off-by-one error in loop condition
• Initializing prefix incorrectly
• Misusing string methods

5. Given the array ["interview", "interval", "internal", "internet"], what is the longest common prefix? Also, explain why the prefix stops where it does.

hard

A. "inte" because all strings start with these four letters

B. "in" because only first two letters are common

C. "int" because the sixth letter differs in some strings

D. "inter" because all strings start with these five letters

Solution

1. Step 1: Compare characters one by one

   Check each character index across all strings: 'i', 'n', 't', 'e', 'r' are common in all.

2. Step 2: Identify where mismatch occurs

   At index 5, 'v' in "interview" and "interval", but 'n' in "internal" and "internet", so prefix stops at "inter".

3. Final Answer:

   "inter" because all strings start with these five letters -> Option D

4. Quick Check:

   Common start "inter" = B [OK]

Hint: Check each character position until mismatch found [OK]

Common Mistakes:

• Assuming prefix is longer than actual common part
• Ignoring character positions carefully
• Confusing similar but different letters