Longest Common Prefix in DSA Go - Execution Trace

Concept Flow - Longest Common Prefix

Start with first string as prefix

↓

For each next string in array

↓

Compare prefix with current string

↓

Shorten prefix until it matches start of current string

↓

If prefix empty, stop and return empty string

↓

After all strings processed

↓

Return prefix

Start with the first word as the prefix. For each next word, shorten the prefix until it matches the start of that word. Stop if prefix becomes empty. Return the prefix after all words.

Execution Sample

DSA Go

import "strings"

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

Finds the longest common prefix string among an array of strings by shrinking the prefix until it matches all strings.

Execution Table

Step	Operation	Current String	Prefix Before	Prefix After	Visual State
1	Initialize prefix	N/A	N/A	flower	Prefix = 'flower'
2	Compare with 'flow'	flow	flower	flow	Prefix shortened to 'flow' because 'flow' starts with 'flow'
3	Compare with 'flight'	flight	flow	fl	Prefix shortened to 'fl' because 'flight' starts with 'fl'
4	All strings processed	N/A	fl	fl	Final prefix is 'fl'

💡 All strings processed or prefix became empty; final prefix returned

Variable Tracker

Variable	Start	After Step 2	After Step 3	Final
prefix	flower	flow	fl	fl
current string	N/A	flow	flight	N/A

Key Moments - 2 Insights

Why do we shorten the prefix instead of checking the whole string each time?

Because the prefix must be common to all strings, we reduce it step-by-step until it matches the start of the current string, as shown in steps 2 and 3 of the execution_table.

What happens if the prefix becomes empty?

If prefix becomes empty, it means no common prefix exists. The code returns an empty string immediately, as seen in the inner loop condition in the code and explained in the concept_flow.

Visual Quiz - 3 Questions

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

A flower

B flow

C fl

D flight

💡 Hint

Check Step 2 in the execution_table where prefix changes after comparing with 'flow'

At which step does the prefix become 'fl'?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at Step 3 in the execution_table where prefix changes after comparing with 'flight'

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

A It would become 'd'

B It would become 'do'

C It would become empty string

D It would remain 'dog'

💡 Hint

Since no common prefix exists, prefix shortens to empty string and returns, as explained in key_moments

Concept Snapshot

Longest Common Prefix:
- Start prefix as first string
- For each next string, shorten prefix until it matches start
- If prefix empty, return ""
- After all strings, return prefix
- Uses string prefix checking and slicing

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 in the array. 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 the prefix becomes empty, the function returns an empty string immediately, indicating no common prefix. After processing all strings, the remaining prefix is returned as the longest common prefix.

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