# 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/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode.realtemirov.uz/problems/14.-longest-common-prefix.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.