# LeetCode 1002: Find Common Characters

## Problem Restatement

We are given an array of strings `words`.

We need to return a list of all characters that appear in every string in `words`, including duplicates.

If a character appears `k` times in every string, we include it `k` times in the answer.

The answer can be returned in any order.

The official constraints state that `1 <= words.length <= 100`, `1 <= words[i].length <= 100`, and each `words[i]` contains only lowercase English letters.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Array of strings `words` |
| Output | List of characters common to all words |
| Duplicates | Include as many copies as appear in every word |

Function shape:

```python
def commonChars(words: list[str]) -> list[str]:
    ...
```

## Examples

Example 1:

```python
words = ["bella", "label", "roller"]
```

Character frequencies:

| Char | "bella" | "label" | "roller" | Min |
|---|---:|---:|---:|---:|
| b | 1 | 1 | 0 | 0 |
| e | 1 | 1 | 1 | 1 |
| l | 2 | 2 | 2 | 2 |
| r | 0 | 0 | 2 | 0 |

Common characters:

```python
["e", "l", "l"]
```

Example 2:

```python
words = ["cool", "lock", "cook"]
```

Character frequencies:

| Char | "cool" | "lock" | "cook" | Min |
|---|---:|---:|---:|---:|
| c | 1 | 1 | 2 | 1 |
| o | 2 | 1 | 2 | 1 |
| l | 1 | 1 | 0 | 0 |
| k | 0 | 1 | 1 | 0 |

Common characters:

```python
["c", "o"]
```

## Key Insight

A character is common to all words if and only if its minimum frequency across all words is at least 1.

The number of times we include a character is its minimum frequency across all words.

So we compute the element-wise minimum of the frequency arrays for all words.

## Algorithm

1. Start with the frequency array of the first word.
2. For each subsequent word, take the element-wise minimum with the current minimum array.
3. Expand the final minimum array into a character list.

## Correctness

A character `c` appears at least `min_freq[c]` times in every word because `min_freq[c]` is the minimum frequency of `c` across all words.

We include `c` exactly `min_freq[c]` times. This is the maximum number of copies of `c` we can include while guaranteeing each copy appears in every word.

## Edge Cases

- Duplicates usually matter; store counts when a set would lose necessary multiplicity.
- Update the frequency structure in the same order the invariant assumes.
- Check empty or one-element inputs if the problem allows them.

## Complexity

Let `n = len(words)` and `m` be the average word length.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n * m)` | Process every character in every word |
| Space | `O(1)` | Frequency arrays are always size 26 |

## Common Pitfalls

- Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
- Prefer problem-specific names over one-letter variables once the logic becomes stateful.

## Implementation

```python
from collections import Counter

class Solution:
    def commonChars(self, words: list[str]) -> list[str]:
        min_freq = Counter(words[0])

        for word in words[1:]:
            word_freq = Counter(word)
            for ch in min_freq:
                min_freq[ch] = min(min_freq[ch], word_freq.get(ch, 0))

        result = []
        for ch, count in min_freq.items():
            result.extend([ch] * count)

        return result
```

## Code Explanation

Initialize the minimum frequency from the first word:

```python
min_freq = Counter(words[0])
```

For each following word, reduce counts to the minimum:

```python
for ch in min_freq:
    min_freq[ch] = min(min_freq[ch], word_freq.get(ch, 0))
```

If a character from `words[0]` does not appear in a later word, its count drops to `0`.

Expand the final counts into a list:

```python
result.extend([ch] * count)
```

## Testing

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

    assert sorted(s.commonChars(["bella", "label", "roller"])) == sorted(["e", "l", "l"])
    assert sorted(s.commonChars(["cool", "lock", "cook"])) == sorted(["c", "o"])
    assert sorted(s.commonChars(["abc", "abc"])) == sorted(["a", "b", "c"])
    assert s.commonChars(["a", "b"]) == []

    print("all tests passed")

run_tests()
```

| Test | Expected | Why |
|---|---|---|
| `["bella","label","roller"]` | `["e","l","l"]` | Standard example |
| `["cool","lock","cook"]` | `["c","o"]` | Standard example |
| `["abc","abc"]` | `["a","b","c"]` | Identical words |
| `["a","b"]` | `[]` | No characters in common |