Longest Common Prefix in DSA Go

Mental Model

Find the longest starting part that all strings share. We compare characters one by one until a difference appears.

Analogy: Imagine several friends starting a race together. The longest common prefix is like the longest stretch of road where all friends run side by side before someone takes a different path.

Strings:
[flower]
[flow]
[flight]

Longest Common Prefix:
[f l]
↑ ↑

Dry Run Walkthrough

Input: list: ["flower", "flow", "flight"]

Goal: Find the longest prefix common to all strings

Step 1: Compare first characters of all strings

[flower, flow, flight]
Characters compared: 'f', 'f', 'f'

Why: All start with 'f', so prefix can start with 'f'

Step 2: Compare second characters of all strings

[flower, flow, flight]
Characters compared: 'l', 'l', 'l'

Why: All have 'l' as second character, prefix extends to 'fl'

Step 3: Compare third characters of all strings

[flower, flow, flight]
Characters compared: 'o', 'o', 'i'

Why: Mismatch found ('o' vs 'i'), stop comparison

Result:

Longest common prefix: 'fl'

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	prefix := strs[0]
	for i := 1; i < len(strs); i++ {
		j := 0
		for j < len(prefix) && j < len(strs[i]) && prefix[j] == strs[i][j] {
			j++ // advance j while characters match
		}
		prefix = prefix[:j] // shorten prefix to matched part
		if prefix == "" {
			break // no common prefix
		}
	}
	return prefix
}

func main() {
	words := []string{"flower", "flow", "flight"}
	result := longestCommonPrefix(words)
	fmt.Println(result)
}

prefix := strs[0]

start prefix as first string to compare with others

for i := 1; i < len(strs); i++ {

iterate over each string after the first

for j := 0; j < len(prefix) && j < len(strs[i]) && prefix[j] == strs[i][j]; j++ {

compare characters one by one until mismatch or end

prefix = prefix[:j]

update prefix to matched substring

if prefix == "" { break }

stop early if no common prefix remains

Output

fl

Complexity Analysis

Time: O(S) because we compare characters of all strings up to the shortest prefix length, where S is the sum of all characters in all strings

Space: O(1) because we only store the prefix string and indexes, no extra data structures proportional to input size

vs Alternative: Compared to checking all pairs repeatedly, this approach is efficient by progressively shortening the prefix, avoiding repeated full comparisons

Edge Cases

empty list

returns empty string immediately

DSA Go

if len(strs) == 0 { return "" }

list with one string

returns that string as prefix

DSA Go

prefix := strs[0]

no common prefix

returns empty string after first mismatch

DSA Go

if prefix == "" { break }

When to Use This Pattern

When you need to find a shared starting part among many strings, use the Longest Common Prefix pattern by comparing characters step by step.

Common Mistakes

Mistake: Not checking string length before accessing characters, causing index errors
Fix: Always check current index is less than both strings' lengths before comparing characters

Mistake: Comparing all pairs of strings instead of progressively shortening prefix
Fix: Use the first string as prefix and shorten it by comparing with each string once

Summary

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

Use when you want to find shared beginnings among multiple strings efficiently.

Compare characters one by one across all strings, shortening prefix at first mismatch.

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 substring unique to each string

Solution

1. Step 1: Understand the prefix concept

   A prefix is a substring starting at the beginning of a string.

2. Step 2: Define longest common prefix

   The longest common prefix is the longest substring starting at 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 = longest common start substring [OK]

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

Common Mistakes:

• Confusing prefix with substring anywhere
• Thinking about suffix instead of prefix
• Assuming shortest substring is the answer

2. Which of the following Go code snippets correctly initializes a slice of strings named strs with values "flower", "flow", "flight"?

easy

A. var strs = {"flower", "flow", "flight"}

B. strs := [3]string{"flower", "flow", "flight"}

C. strs := []string{"flower", "flow", "flight"}

D. strs := string{"flower", "flow", "flight"}

Solution

1. Step 1: Identify correct slice initialization syntax

   In Go, slices are initialized with []type{values} syntax.

2. Step 2: Check each option

   strs := []string{"flower", "flow", "flight"} uses []string with curly braces correctly. strs := [3]string{"flower", "flow", "flight"} uses array syntax but is valid but fixed size, not slice. var strs = {"flower", "flow", "flight"} uses invalid braces. strs := string{"flower", "flow", "flight"} uses wrong type syntax.

3. Final Answer:

   strs := []string{"flower", "flow", "flight"} -> Option C

4. Quick Check:

   Slice syntax = []type{values} [OK]

Hint: Use []string{...} to create string slices in Go [OK]

Common Mistakes:

• Using array syntax when slice is needed
• Missing type brackets []
• Using curly braces without type

3. Given a list of strings ["dog", "racecar", "car"], what should the longest common prefix function return and why?

easy

A. "d" because all strings start with 'd'

B. "" because no common prefix exists

C. "c" because 'car' is the shortest string

D. "r" because 'racecar' starts with 'r'

Solution

1. Step 1: Compare prefixes of all strings

   "dog" starts with 'd', "racecar" with 'r', "car" with 'c'. No common starting character exists.

2. Step 2: Determine longest common prefix

   Since no common starting substring exists, the longest common prefix is empty string "".

3. Final Answer:

   "" because no common prefix exists -> Option B

4. Quick Check:

   No common start means empty prefix [OK]

Hint: If first chars differ, prefix is empty [OK]

Common Mistakes:

• Assuming shortest string is prefix
• Picking first string's first letter
• Ignoring all strings must share prefix

4. What is the output of the following Go code that finds the longest common prefix?

package main
import "fmt"
func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    prefix := strs[0]
    for _, s := range strs[1:] {
        for len(prefix) > 0 && len(s) >= len(prefix) && s[:len(prefix)] != prefix {
            prefix = prefix[:len(prefix)-1]
        }
    }
    return prefix
}
func main() {
    strs := []string{"inter", "internet", "internal"}
    fmt.Println(longestCommonPrefix(strs))
}

medium

A. int

B. in

C. inte

D. inter

Solution

1. Step 1: Initialize prefix and compare with each string

   Prefix starts as "inter". Compare with "internet": len(s)=8 >=5 and "internet"[:5] == "inter", so no reduction.

2. Step 2: Compare prefix "inter" with "internal"

   len(s)=8 >=5 and "internal"[:5] == "inter", so prefix remains "inter".

3. Final Answer:

   inter -> Option D

4. Quick Check:

   Common start of all strings = "inter" [OK]

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

Common Mistakes:

• Not shrinking prefix correctly
• Comparing prefix with wrong substring
• Returning initial prefix without checks

5. Identify the bug in this Go function for longest common prefix and select the fix:

func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    prefix := strs[0]
    for _, s := range strs[1:] {
        for len(prefix) > 0 && s[:len(prefix)] != prefix {
            prefix = prefix[:len(prefix)-1]
        }
    }
    return prefix
}

medium

A. Add check that len(s) >= len(prefix) before s[:len(prefix)]

B. Initialize prefix as empty string instead of strs[0]

C. Change for loop to iterate over all strings including first

D. Return strs[0] directly without loop

Solution

1. Step 1: Analyze substring slicing in loop

   The code slices s[:len(prefix)] without checking if s is long enough, causing runtime panic if s is shorter than prefix.

2. Step 2: Fix by adding length check

   Adding condition len(s) >= len(prefix) before slicing prevents out-of-range error.

3. Final Answer:

   Add check that len(s) >= len(prefix) before s[:len(prefix)] -> Option A

4. Quick Check:

   Prevent slice out-of-range by length check [OK]

Hint: Always check slice length before slicing [OK]

Common Mistakes:

• Ignoring string length before slicing
• Changing prefix initialization unnecessarily
• Skipping loop over all strings