Longest Common Prefix in DSA Typescript

Mental Model

Find the longest starting part that all words share exactly.

Analogy: Imagine several friends saying their names out loud. The longest common prefix is like the longest sound at the start of all their names that sounds the same.

words: [flower, flow, flight]
          ↑       ↑      ↑
common prefix: [fl]

Dry Run Walkthrough

Input: words: [flower, flow, flight]

Goal: Find the longest prefix shared by all words

Step 1: Start with prefix = 'flower' (the first word)

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 'flow'

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

Why: Remove characters from prefix until it matches the start of 'flow'

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

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

Why: Remove characters from prefix until it matches the start of 'flight'

Step 4: No more words to check, prefix 'fl' is longest common prefix

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

Why: All words start with 'fl', so this is the answer

Result:

prefix = 'fl'

Annotated Code

DSA Typescript

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

// Driver code
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 the first word

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

iterate over remaining words to compare prefix

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

reduce prefix until it matches start of current word

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

remove last character from prefix to shorten it

if (prefix === '') return '';

if prefix is empty, no common prefix exists

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 all pairs or building a trie, this approach is simpler and uses less space

Edge Cases

empty list

returns empty string immediately

DSA Typescript

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

list with one word

returns that word as prefix

DSA Typescript

let prefix = strs[0];

no common prefix

returns empty string after reducing prefix to empty

DSA Typescript

if (prefix === '') return '';

When to Use This Pattern

When you need to find the longest shared start among many strings, use the longest common prefix pattern to compare and shorten a candidate prefix.

Common Mistakes

Mistake: Not checking if the prefix is at the start of the current word, leading to wrong prefix
Fix: Use indexOf(prefix) === 0 to ensure prefix matches start of word

Mistake: Not handling empty input list causing errors
Fix: Add a guard 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 want to find shared beginnings in multiple words or strings.

Start with the first word as prefix and shorten it until all words start with it.

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