> For the complete documentation index, see [llms.txt](https://leetcode.realtemirov.uz/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode.realtemirov.uz/problems/14.-longest-common-prefix.md).

# 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

```go
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)

```go
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](/files/Xi8ouwpQBdLva58xad9N)

Leetcode: [link](https://leetcode.com/problems/longest-common-prefix/description/)