Longest Common Prefix in DSA C# - 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 C#

string LongestCommonPrefix(string[] strs) {
  if (strs == null || strs.Length == 0) return "";
  string prefix = strs[0];
  for (int i = 1; i < strs.Length; i++) {
    while (!strs[i].StartsWith(prefix)) {
      prefix = prefix.Substring(0, prefix.Length - 1);
      if (prefix == "") return "";
    }
  }
  return prefix;
}

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

Execution Table

Step	Operation	Current String	Prefix Before	Prefix After	Visual State
1	Initialize prefix	N/A	N/A	flower	[flower]
2	Compare prefix with 'flow'	flow	flower	flow	[flow]
3	Compare prefix with 'flight'	flight	flow	fl	[fl]
4	No more strings	N/A	fl	fl	[fl]

💡 All strings processed, prefix 'fl' is longest common prefix

Variable Tracker

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

Key Moments - 3 Insights

Why do we shrink the prefix inside a while loop?

Because the prefix might not match the current string at once, so we remove one character at a time until it matches or becomes empty, as shown in step 2 and 3 of the execution_table.

What happens if the prefix becomes empty?

The function returns an empty string immediately, meaning no common prefix exists. This is checked inside the while loop in the code and would stop execution early.

Why start prefix with the first string?

Starting with the first string ensures the prefix is at most as long as any string. We then reduce it to fit all strings, as seen in step 1 of the execution_table.

Visual Quiz - 3 Questions

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

A flower

B fl

C flow

D flight

💡 Hint

Check the 'Prefix After' column at Step 2 in the execution_table.

At which step does the prefix shrink to 'fl'?

A Step 3

B Step 2

C Step 1

D Step 4

💡 Hint

Look at the 'Prefix After' column in the execution_table for Step 3.

If the input array had a string 'f', what would happen to the prefix?

A It would remain 'fl'

B It would shrink to 'f'

C It would become empty immediately

D It would become 'flower'

💡 Hint

Consider how the prefix shrinks to match each string as shown in the code and execution_table.

Concept Snapshot

Longest Common Prefix:
- Start prefix as first string
- For each string, shrink prefix until it matches start
- If prefix empty, return ""
- Return prefix after all strings
- Uses substring and startsWith methods

Full Transcript

The Longest Common Prefix algorithm starts by taking the first string as the initial prefix. Then, it compares this prefix with each subsequent string. If the current string does not start with the prefix, the prefix is shortened by removing the last character. This process repeats until the prefix matches the start of the current string or becomes empty. If empty, the function returns an empty string, meaning no common prefix exists. Otherwise, after all strings are processed, the remaining prefix is the longest common prefix. The execution table shows how the prefix changes step by step with each string comparison.

Practice

1. What does the Longest Common Prefix (LCP) problem ask for when given an array of strings?

easy

A. The longest starting substring common to all strings

B. The longest substring found anywhere in all strings

C. The shortest string in the array

D. The number of strings in the array

Solution

1. Step 1: Understand the problem definition

   The Longest Common Prefix problem asks for the longest substring that appears at the start of every string in the array.

2. Step 2: Compare options with the definition

   The longest starting substring common to all strings matches the definition exactly. Options A, B, and C do not describe the prefix or the problem correctly.

3. Final Answer:

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

4. Quick Check:

   Longest Common Prefix = longest starting substring [OK]

Hint: Focus on the start of strings, not anywhere inside [OK]

Common Mistakes:

• Confusing prefix with substring anywhere
• Thinking about shortest string instead
• Counting strings instead of prefix

2. Which of the following C# method signatures is correct for a function that finds the longest common prefix of a string array?

easy

A. public void LongestCommonPrefix(string[] strs)

B. public int LongestCommonPrefix(string[] strs)

C. public string LongestCommonPrefix(string[] strs)

D. public string LongestCommonPrefix(List<string> strs)

Solution

1. Step 1: Identify the expected return type

   The longest common prefix is a string, so the method should return a string.

2. Step 2: Check parameter type and return type

   public string LongestCommonPrefix(string[] strs) returns string and takes string array, which is correct. public int LongestCommonPrefix(string[] strs) returns int (wrong type). public void LongestCommonPrefix(string[] strs) returns void (no return). public string LongestCommonPrefix(List<string> strs) uses List<string> instead of array, which is valid but not matching the question's array input.

3. Final Answer:

   public string LongestCommonPrefix(string[] strs) -> Option C

4. Quick Check:

   Return type string with string[] parameter [OK]

Hint: Return string, input string array for LCP method [OK]

Common Mistakes:

• Using wrong return type like int or void
• Using List<string> instead of string[] when array expected
• Confusing parameter types

3. What is the output of the following C# code?

string[] words = {"flower", "flow", "flight"};
string prefix = LongestCommonPrefix(words);
Console.WriteLine(prefix);

string LongestCommonPrefix(string[] strs) {
    if (strs == null || strs.Length == 0) return "";
    string prefix = strs[0];
    for (int i = 1; i < strs.Length; i++) {
        while (!strs[i].StartsWith(prefix)) {
            prefix = prefix.Substring(0, prefix.Length - 1);
            if (prefix == "") return "";
        }
    }
    return prefix;
}

medium

A. "fl"

B. "flow"

C. "f"

D. "flight"

Solution

1. Step 1: Initialize prefix and iterate

   Prefix starts as "flower". Compare with "flow": "flow" does not start with "flower", so remove last char -> "flowe", then "flow", which matches.

2. Step 2: Compare prefix with "flight"

   "flight" does not start with "flow", remove last char: "flo", no; "fl", yes. So prefix becomes "fl".

3. Final Answer:

   "fl" -> Option A

4. Quick Check:

   Common prefix of all = "fl" [OK]

Hint: Shrink prefix until all strings start with it [OK]

Common Mistakes:

• Assuming prefix is first string always
• Not shrinking prefix correctly
• Returning empty string too early

4. The following code attempts to find the longest common prefix but has a bug. What is the bug?

string LongestCommonPrefix(string[] strs) {
    if (strs == null || strs.Length == 0) return "";
    string prefix = strs[0];
    for (int i = 1; i < strs.Length; i++) {
        while (!strs[i].Contains(prefix)) {
            prefix = prefix.Substring(0, prefix.Length - 1);
            if (prefix == "") return "";
        }
    }
    return prefix;
}

medium

A. Not checking for null strings inside array

B. Using Contains instead of StartsWith causes wrong prefix check

C. Prefix is not updated inside the loop

D. Loop index starts from 0 instead of 1

Solution

1. Step 1: Analyze the prefix check method

   The code uses strs[i].Contains(prefix) to check prefix, but prefix must be at the start, so StartsWith is correct.

2. Step 2: Understand impact of Contains

   Contains allows prefix anywhere in the string, so it may accept wrong prefixes that are not at the start.

3. Final Answer:

   Using Contains instead of StartsWith causes wrong prefix check -> Option B

4. Quick Check:

   Prefix must be at start, not anywhere [OK]

Hint: Use StartsWith, not Contains, to check prefix [OK]

Common Mistakes:

• Using Contains instead of StartsWith
• Ignoring null or empty strings in array
• Incorrect loop start index

5. Given the array ["interview", "interrupt", "integrate", "integral"], what is the longest common prefix? Also, explain why the prefix ends where it does.

hard

A. "integ"

B. "inte"

C. "inter"

D. "int"

Solution

1. Step 1: Compare strings character by character

   All strings start with "int". "interview" and "interrupt" continue with "er", while "integrate" and "integral" continue with "eg".

2. Step 2: Identify where prefix breaks

   "interview" and "interrupt" have "inter", but "integrate" and "integral" have "integ", so common prefix stops at "int".

3. Final Answer:

   "int" -> Option D

4. Quick Check:

   Prefix stops where any string differs [OK]

Hint: Prefix ends at first differing character among strings [OK]

Common Mistakes:

• Assuming longer prefix without checking all strings
• Ignoring difference in later strings
• Confusing similar prefixes with actual common prefix