# LeetCode 14: Longest Common Prefix

## Problem Restatement

We are given an array of strings `strs`.

We need to find the longest string that appears at the beginning of every string in the array.

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

For example:

```text
["flower", "flow", "flight"]
```

All strings start with:

```text
"fl"
```

So the answer is:

```text
"fl"
```

The LeetCode statement asks for the longest common prefix string among an array of strings, returning `""` when no common prefix exists.

## Input and Output

| Item | Meaning |
|---|---|
| Input | An array of strings `strs` |
| Output | The longest common prefix |
| No common prefix | Return `""` |
| Constraint | `1 <= strs.length <= 200` |
| Constraint | `0 <= strs[i].length <= 200` |
| Characters | Lowercase English letters if the string is non-empty |

Example function shape:

```python
def longestCommonPrefix(strs: list[str]) -> str:
    ...
```

## Examples

Example 1:

```text
strs = ["flower", "flow", "flight"]
```

Compare characters from the start:

```text
flower
flow
flight
```

The first character is `f` in every string.

The second character is `l` in every string.

At the third character:

```text
flower -> o
flow   -> o
flight -> i
```

They differ.

Output:

```text
"fl"
```

Example 2:

```text
strs = ["dog", "racecar", "car"]
```

The first characters are:

```text
d
r
c
```

They already differ.

Output:

```text
""
```

Example 3:

```text
strs = [""]
```

The only string is empty.

Output:

```text
""
```

## First Thought: Shrink a Candidate Prefix

A simple approach is to start with the first string as the candidate prefix.

Then compare it with every other string.

Whenever a string does not start with the current prefix, remove the last character from the prefix.

Code:

```python
class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        prefix = strs[0]

        for word in strs[1:]:
            while not word.startswith(prefix):
                prefix = prefix[:-1]

                if prefix == "":
                    return ""

        return prefix
```

This works, but repeated slicing can create extra string copies.

We can solve it more directly by comparing characters column by column.

## Key Insight

A common prefix must match at the same index in every string.

So we can use the first string as a reference.

For each index `i` in the first string:

1. Read `strs[0][i]`.
2. Check whether every other string has the same character at index `i`.
3. If any string is too short or has a different character, return `strs[0][:i]`.

This stops exactly where the common prefix ends.

## Visual Walkthrough

Use:

```text
strs = ["flower", "flow", "flight"]
```

Use `"flower"` as the reference.

Index `0`:

```text
flower[0] = f
flow[0]   = f
flight[0] = f
```

All match.

Index `1`:

```text
flower[1] = l
flow[1]   = l
flight[1] = l
```

All match.

Index `2`:

```text
flower[2] = o
flow[2]   = o
flight[2] = i
```

Mismatch.

Return:

```text
strs[0][:2] = "fl"
```

## Algorithm

1. Choose the first string as the reference.
2. For each index `i` in the reference:
   - compare the character at index `i` with every other string
   - if another string has ended, return the prefix before `i`
   - if another string has a different character, return the prefix before `i`
3. If all characters in the first string match, return the first string.

## Correctness

The algorithm checks prefix characters from left to right.

For every index before the stopping point, all strings have the same character. Therefore `strs[0][:i]` is a common prefix.

The algorithm stops at the first index where at least one string either has no character or has a different character. No longer prefix can be common, because a longer prefix would need all strings to match at that index.

If the algorithm never stops, then every character of the first string appears at the beginning of every other string. So the first string itself is the longest common prefix.

Therefore the algorithm returns exactly the longest common prefix.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(S)` | We inspect characters until the first mismatch or until all prefix characters are checked |
| Space | `O(1)` | Only indices are stored |

Here `S` is the total number of characters inspected. In the worst case, this is the total length of all strings.

## Implementation

```python
class Solution:
    def longestCommonPrefix(self, strs: list[str]) -> str:
        first = strs[0]

        for i, char in enumerate(first):
            for word in strs[1:]:
                if i == len(word) or word[i] != char:
                    return first[:i]

        return first
```

## Code Explanation

Use the first string as the reference:

```python
first = strs[0]
```

Scan each character of the reference:

```python
for i, char in enumerate(first):
```

Compare that character with the same position in every other word:

```python
for word in strs[1:]:
```

If a word is shorter, the common prefix ends before index `i`:

```python
i == len(word)
```

If the character differs, the common prefix also ends before index `i`:

```python
word[i] != char
```

So we return:

```python
return first[:i]
```

If the loop completes, the whole first string is common to all strings:

```python
return first
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.longestCommonPrefix(["flower", "flow", "flight"]) == "fl"
    assert s.longestCommonPrefix(["dog", "racecar", "car"]) == ""
    assert s.longestCommonPrefix([""]) == ""
    assert s.longestCommonPrefix(["a"]) == "a"
    assert s.longestCommonPrefix(["ab", "a"]) == "a"
    assert s.longestCommonPrefix(["same", "same", "same"]) == "same"
    assert s.longestCommonPrefix(["cir", "car"]) == "c"

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `["flower", "flow", "flight"]` | Standard shared prefix |
| `["dog", "racecar", "car"]` | No common prefix |
| `[""]` | Empty single string |
| `["a"]` | Single non-empty string |
| `["ab", "a"]` | One string is prefix of another |
| `["same", "same", "same"]` | All strings equal |
| `["cir", "car"]` | Mismatch after first character |