Longest Common Prefix in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Longest Common Prefix Function

What is the output of the following Go code that finds the longest common prefix among strings?

DSA Go

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() {
	words := []string{"flower", "flow", "flight"}
	fmt.Println(longestCommonPrefix(words))
}

A ""

B "f"

C "fl"

D "flow"

💡 Hint

Check how the prefix is shortened when it doesn't match the start of each string.

The function starts with the first string as the prefix. It then compares this prefix with each string in the list. If the current prefix is not a prefix of the string, it shortens the prefix by one character from the end until it matches or becomes empty. For the input ["flower", "flow", "flight"], the longest common prefix is "fl".

❓ Predict Output

intermediate

Longest Common Prefix with Empty String Present

What will be the output of this Go code when one of the strings is empty?

DSA Go

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() {
	words := []string{"", "b", "c"}
	fmt.Println(longestCommonPrefix(words))
}

A ""

B "b"

C "c"

D runtime error

💡 Hint

An empty string means no common prefix can exist.

Since one of the strings is empty, the longest common prefix must be empty. The function returns an empty string "".

🔧 Debug

advanced

Identify the Bug in Longest Common Prefix Code

What error will this Go code produce when run, and why?

DSA Go

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() {
	words := []string{"dog", "racecar", "car"}
	fmt.Println(longestCommonPrefix(words))
}

A compilation error

B ""

C "d"

D runtime error: slice bounds out of range

💡 Hint

Check if the code safely handles cases where the prefix length is longer than the string length.

The code does not check if the current string is shorter than the prefix before slicing. When s is shorter than prefix, s[:len(prefix)] causes a runtime error due to out-of-range slicing.

🧠 Conceptual

advanced

Longest Common Prefix Algorithm Complexity

What is the time complexity of the standard longest common prefix algorithm that compares characters one by one among all strings?

A O(S) where S is the sum of all characters in all strings

B O(N^2) where N is the number of strings

C O(1) constant time

D O(N * log N) where N is the number of strings

💡 Hint

Consider how many characters are compared in total across all strings.

The algorithm compares characters one by one across all strings until a mismatch is found. In the worst case, it compares all characters of all strings, so the complexity is O(S), where S is the total number of characters.

🚀 Application

expert

Longest Common Prefix in a Trie Data Structure

Given a trie built from the strings ["interview", "interrupt", "integrate", "integral"], what is the longest common prefix stored in the trie?

A "inte"

B "int"

C "inter"

D "integr"

💡 Hint

Find the deepest node in the trie where all strings share the same path.

All strings start with "int". After "int", the strings diverge: "erview", "errupt", "egrate", "egral". So the longest common prefix is "int".

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