14. Longest Common Prefix

🟩 Easy

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1

Input: strs = ["flower","flow","flight"] Output: "fl"

Example 2

Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

Constraints

• 1 <= strs.length <= 200

• 0 <= strs[i].length <= 200

• strs[i] consists of only lowercase English letters.

Solution

My Solution

func longestCommonPrefix(strs []string) string {
    if len(strs) == 1 {
        return strs[0]
    }

    prefix := strs[0]

    for i := 1; i < len(strs); i++ {
        for strings.Index(strs[i], prefix) != 0 {
            prefix = prefix[:len(prefix)-1]
        }
    }

    return prefix
}

Optimal Solution (Vertical Scanning)

func longestCommonPrefix(strs []string) string {
    if len(strs) == 0 {
        return ""
    }
    
    // Use first string as initial prefix
    for i := 0; i < len(strs[0]); i++ {
        c := strs[0][i]
        
        // Compare this character with same position in other strings
        for j := 1; j < len(strs); j++ {
            // If we've reached the end of any string
            // or found a mismatch, return current prefix
            if i >= len(strs[j]) || strs[j][i] != c {
                return strs[0][:i]
            }
        }
    }
    
    // If we get here, first string is the prefix
    return strs[0]
}

Approach

This solution uses vertical scanning to find the common prefix:

1. Key Insight:

   • Common prefix must be present at the start of all strings

   • Can scan character by character vertically across all strings

   • First mismatch determines prefix length

2. Implementation Strategy:

   • Use first string as reference

   • Compare each character with same position in all strings

   • Stop at first mismatch or end of any string

3. Processing Rules:

   • Empty array returns empty string

   • Single string returns itself

   • Prefix ends at first mismatch or shortest string length

Complexity Analysis

Time Complexity: O(S)

• S is sum of all characters in all strings

• In worst case, all strings are identical

• Each character compared exactly once

• Early termination on mismatch improves average case

Space Complexity: O(1)

• Only constant extra space used:

  • Two loop counters

  • One character variable

  • No additional data structures

Why it works

• String Properties:

  • Common prefix must start at beginning

  • Length limited by shortest string

  • Case-sensitive comparison (all lowercase)

• Optimization Details:

  • No string concatenation needed

  • Early termination on mismatch

  • Direct byte comparison (no conversion needed)

  • Uses string slicing for result

• Key Improvements over Original:

  • No repeated substring operations

  • No string.Index calls (more efficient)

  • Single pass through characters

  • Better early termination

• Edge Cases Handled:

  • Empty array

  • Single string

  • No common prefix

  • Different length strings

  • First string is prefix of all

result

Leetcode: link