Longest Common Prefix in DSA Typescript - Execution Trace

Concept Flow - Longest Common Prefix

Start with first string as prefix

↓

Compare prefix with next string

↓

Find common prefix between prefix and string

↓

Update prefix

↓

More strings?

Yes→Repeat comparison

No↓

Return prefix

Start with the first string as the prefix. Compare it with each next string to find the common prefix. Update the prefix each time. Stop when no more strings or prefix is empty.

Execution Sample

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;
}

This code finds the longest common prefix string among an array of strings by shrinking the prefix until it matches the start of each string.

Execution Table

Step	Operation	Current Prefix	String Compared	Prefix Update	Visual State
1	Initialize prefix	"flower"	N/A	prefix = "flower"	[flower]
2	Compare prefix with "flow"	"flower"	"flow"	prefix shrinks to "flow"	[flow]
3	Compare prefix with "flight"	"flow"	"flight"	prefix shrinks to "fl"	[fl]
4	No more strings	"fl"	N/A	Return prefix "fl"	[fl]

💡 All strings compared or prefix became empty; final prefix is "fl"

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
prefix	"flower"	"flow"	"fl"	"fl"
i	0	1	2	3

Key Moments - 3 Insights

Why do we shrink the prefix inside a while loop instead of just once?

Because the prefix might need to shrink multiple times until it matches the start of the current string, as shown in step 3 where prefix shrinks from "flow" to "fl".

What happens if the input array is empty?

The function returns an empty string immediately, as shown in the code's first line and no steps in the execution table.

Why do we check if the current string starts with the prefix?

Because the prefix must be at the start of each string to be common; if not, we shrink it until it fits or becomes empty, as shown in steps 2 and 3.

Visual Quiz - 3 Questions

Look at the execution table, what is the prefix after comparing with the second string?

A "flow"

B "flower"

C "fl"

D "flight"

💡 Hint

Check the 'Current Prefix' and 'Prefix Update' columns at Step 2 in the execution table.

At which step does the prefix become "fl"?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at the 'Prefix Update' column and 'Current Prefix' at Step 3.

If the input array was ["dog", "racecar", "car"], what would happen to the prefix?

A It would remain "dog"

B It would shrink to "d"

C It would become empty string ""

D It would become "car"

💡 Hint

Think about the prefix shrinking when no common start exists among all strings.

Concept Snapshot

Longest Common Prefix:
- Start prefix as first string
- Compare prefix with each string
- Shrink prefix until it matches start
- Stop if prefix empty or all strings checked
- Return prefix as result

Full Transcript

The Longest Common Prefix algorithm starts by taking the first string as the initial prefix. It then compares this prefix with each subsequent string in the array. If the current string does not start with the prefix, the prefix is shortened by removing the last character repeatedly until it matches the start of the string or becomes empty. This process continues for all strings. If the prefix becomes empty, it means there is no common prefix. Finally, the prefix is returned as the longest common prefix among all strings.

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