# LeetCode 809: Expressive Words

## Problem Restatement

We are given a string `s` and an array of query strings `words`.

A query word is stretchy if it can be expanded to become exactly `s`.

Expansion works on groups of the same consecutive character. For example, in:

```python
"heeellooo"
```

the groups are:

```python
"h", "eee", "ll", "ooo"
```

A group in the query word may be stretched only if the corresponding group in `s` has length at least `3`.

Return how many words in `words` are stretchy. The official rule is that a query word can be made equal to `s` by extending character groups, where extended groups must reach length at least `3`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A target string `s` and a list of query words |
| Output | Number of stretchy words |
| Stretch operation | Add copies of a character inside one consecutive group |
| Main condition | Character groups must match in order |

## Examples

Example:

```python
s = "heeellooo"
words = ["hello", "hi", "helo"]
```

The word `"hello"` can become `"heeellooo"`:

```python
"h"   -> "h"
"e"   -> "eee"
"ll"  -> "ll"
"o"   -> "ooo"
```

So `"hello"` is stretchy.

The word `"hi"` cannot match because the character groups do not match.

The word `"helo"` cannot match because the target has `"ll"` but the word has only `"l"`. Since the target group length is `2`, it cannot be created by stretching.

So the answer is:

```python
1
```

## First Thought: Build Every Expansion

One possible idea is to generate every string that each word can become after stretching, then check whether `s` appears among them.

This is not practical.

A group can be stretched to many lengths, and generating all possible expanded words would create unnecessary work.

We only need to compare the word against `s` group by group.

## Key Insight

The structure of character groups must be the same.

For example:

```python
s = "heeellooo"
word = "hello"
```

Their groups are:

| String | Groups |
|---|---|
| `s` | `h`, `eee`, `ll`, `ooo` |
| `word` | `h`, `e`, `ll`, `o` |

For each pair of groups:

1. The characters must be the same.
2. The group in `word` cannot be longer than the group in `s`.
3. If the lengths differ, the group in `s` must have length at least `3`.

So a group pair is valid when:

```python
s_count == word_count
```

or:

```python
s_count >= 3 and s_count > word_count
```

If `s_count < 3`, then the counts must be exactly equal.

## Algorithm

Define a helper function:

```python
is_stretchy(s, word)
```

Use two pointers:

| Pointer | Meaning |
|---|---|
| `i` | Current position in `s` |
| `j` | Current position in `word` |

While both pointers are inside their strings:

1. If `s[i] != word[j]`, return `False`.
2. Count the size of the current character group in `s`.
3. Count the size of the current character group in `word`.
4. If the word group is larger, return `False`.
5. If the counts differ and the group in `s` has length less than `3`, return `False`.

At the end, both strings must be fully consumed.

Then count how many words pass this helper.

## Correctness

The helper compares `s` and `word` one character group at a time.

If two corresponding groups have different characters, no sequence of stretch operations can make them equal, because stretching only adds copies inside existing groups and cannot change letters or reorder groups.

If the word group is longer than the target group, it is impossible to shrink it, so the word is not stretchy.

If the group lengths differ and the target group has length less than `3`, the target group could not have been produced by a valid stretch operation. Therefore, the word is not stretchy.

If the target group has length at least `3`, then a shorter matching word group can be stretched to match it.

The helper accepts only when all groups satisfy these conditions and both strings end at the same time. Therefore, it returns `True` exactly for stretchy words.

The main function applies this exact test to every query word, so the final count is correct.

## Complexity

Let `S = len(s)` and let `T` be the total length of all words.

| Metric | Value | Why |
|---|---|---|
| Time | `O(S * len(words) + T)` | Each check scans `s` and one word |
| Space | `O(1)` | Only counters and pointers are stored |

## Implementation

```python
class Solution:
    def expressiveWords(self, s: str, words: list[str]) -> int:
        def is_stretchy(word: str) -> bool:
            i = 0
            j = 0

            while i < len(s) and j < len(word):
                if s[i] != word[j]:
                    return False

                ch = s[i]

                s_start = i
                while i < len(s) and s[i] == ch:
                    i += 1
                s_count = i - s_start

                w_start = j
                while j < len(word) and word[j] == ch:
                    j += 1
                w_count = j - w_start

                if w_count > s_count:
                    return False

                if s_count != w_count and s_count < 3:
                    return False

            return i == len(s) and j == len(word)

        answer = 0

        for word in words:
            if is_stretchy(word):
                answer += 1

        return answer
```

## Code Explanation

The helper starts with two pointers:

```python
i = 0
j = 0
```

They move through `s` and `word`.

If the current characters differ, the group structure cannot match:

```python
if s[i] != word[j]:
    return False
```

We count the current group length in `s`:

```python
s_start = i
while i < len(s) and s[i] == ch:
    i += 1
s_count = i - s_start
```

Then we count the matching group length in `word`:

```python
w_start = j
while j < len(word) and word[j] == ch:
    j += 1
w_count = j - w_start
```

If the word group is too long, it cannot be reduced:

```python
if w_count > s_count:
    return False
```

If the counts differ, the target group must be stretchable:

```python
if s_count != w_count and s_count < 3:
    return False
```

Finally, both strings must end together:

```python
return i == len(s) and j == len(word)
```

This prevents accepting a word that has extra groups or misses groups from `s`.

## Testing

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

    assert sol.expressiveWords("heeellooo", ["hello", "hi", "helo"]) == 1
    assert sol.expressiveWords("zzzzzyyyyy", ["zzyy", "zy", "zyy"]) == 3
    assert sol.expressiveWords("abcd", ["abc"]) == 0
    assert sol.expressiveWords("aaa", ["a", "aa", "aaa", "aaaa"]) == 3
    assert sol.expressiveWords("heeellooo", ["heeellooo", "hello"]) == 2

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `"heeellooo"` sample | Checks normal stretching |
| Large groups in target | Multiple shorter groups can stretch |
| Missing final group | Both strings must end together |
| Target group length `3` | Allows shorter groups but not longer groups |
| Exact match | Exact group counts are valid |