Longest Common Prefix in DSA C#

Mental Model

Find the longest starting part that all words share. It is like looking for the common beginning in a group of words.

Analogy: Imagine several friends start walking from the same place but take different paths. The longest common prefix is the path they all share before splitting.

words: [flower, flow, flight]
common prefix: [fl] ↑
flower -> flow -> flight
^start

Dry Run Walkthrough

Input: words: [flower, flow, flight]

Goal: Find the longest prefix that all words start with

Step 1: Start with the first word 'flower' as the prefix

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

Why: We need a starting prefix to compare with others

Step 2: Compare prefix 'flower' with second word 'flow', shorten prefix to 'flow'

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

Why: Prefix must be common to both words, so shorten to match

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

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

Why: Prefix must be common to all words, so shorten further

Step 4: No more words to compare, final prefix is 'fl'

prefix = 'fl'

Why: All words start with 'fl', so this is longest common prefix

Result:

fl

Annotated Code

DSA C#

using System;

class Program
{
    // Function to find longest common prefix among array of strings
    static string LongestCommonPrefix(string[] strs)
    {
        if (strs == null || strs.Length == 0) return ""; // handle empty input

        string prefix = strs[0]; // start with first word as prefix

        for (int i = 1; i < strs.Length; i++)
        {
            // shorten prefix until it matches start of strs[i]
            while (!strs[i].StartsWith(prefix))
            {
                prefix = prefix.Substring(0, prefix.Length - 1); // remove last char
                if (prefix.Length == 0) return ""; // no common prefix
            }
        }

        return prefix;
    }

    static void Main()
    {
        string[] words = { "flower", "flow", "flight" };
        string result = LongestCommonPrefix(words);
        Console.WriteLine(result);
    }
}

string prefix = strs[0];

start with first word as initial prefix

for (int i = 1; i < strs.Length; i++)

iterate over remaining words to compare prefix

while (!strs[i].StartsWith(prefix))

reduce prefix length until it matches current word start

prefix = prefix.Substring(0, prefix.Length - 1);

remove last character from prefix to shorten it

if (prefix.Length == 0) return "";

if prefix is empty, no common prefix exists

Output

fl

Complexity Analysis

Time: O(S) because we compare characters of all strings until mismatch, where S is total chars in all strings

Space: O(1) because we only store prefix string and no extra data structures

vs Alternative: Compared to comparing all pairs of strings, this approach is efficient by progressively shortening prefix

Edge Cases

empty array

returns empty string immediately

DSA C#

if (strs == null || strs.Length == 0) return "";

array with one string

returns the string itself as prefix

DSA C#

string prefix = strs[0];

no common prefix

prefix shortens to empty string and returns empty

DSA C#

if (prefix.Length == 0) return "";

When to Use This Pattern

When you need to find the common starting part of multiple strings, use the Longest Common Prefix pattern to efficiently find the shared beginning.

Common Mistakes

Mistake: Not checking if the prefix is empty before continuing to shorten it
Fix: Add a check to return empty string immediately if prefix becomes empty

Summary

Finds the longest starting substring common to all strings in the list.

Use when you want to find shared beginnings in multiple strings quickly.

Start with the first string as prefix and shorten it while it doesn't match others.

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