> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Expressive Words Python Solution with Tests

> Tested Python solution for LeetCode 809 with 20 pytest cases. Generate a practice environment with lcpy.

LeetCode 809, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Two Pointers](/catalog/topics/two-pointers), [String](/catalog/topics/string). [View on LeetCode](https://leetcode.com/problems/expressive-words/description/).

Generate this problem as a practice environment: tested reference solution, 20 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 809   # by problem number
lcpy gen -s expressive_words   # by problem name
```

## Problem

Sometimes people repeat letters to represent extra feeling. For example:

* `"hello" -> "heeellooo"`
* `"hi" -> "hiiii"`

In these strings like `"heeellooo"`, we have groups of adjacent letters that are all the same: `"h"`, `"eee"`, `"ll"`, `"ooo"`.

You are given a string `s` and an array of query strings `words`. A query word is **stretchy** if it can be made to be equal to `s` by any number of applications of the following extension operation: choose a group consisting of characters `c`, and add some number of characters `c` to the group so that the size of the group is **three or more**.

* For example, starting with `"hello"`, we could do an extension on the group `"o"` to get `"hellooo"`, but we cannot get `"helloo"` since the group `"oo"` has a size less than three. Also, we could do another extension like `"ll" -> "lllll"` to get `"helllllooo"`. If `s = "helllllooo"`, then the query word `"hello"` would be **stretchy** because of these two extension operations: `query = "hello" -> "hellooo" -> "helllllooo" = s`.

Return *the number of query strings that are **stretchy***.

### Examples

```
Input: s = "heeellooo", words = ["hello", "hi", "helo"]
Output: 1
Explanation:
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more.
```

```
Input: s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"]
Output: 3
```

### Constraints

* `1 <= s.length, words.length <= 100`
* `1 <= words[i].length <= 100`
* `s` and `words[i]` consist of lowercase letters.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/expressive_words/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/expressive_words/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(len(s) + sum(len(w) for w in words))
    # Space: O(len(s)) for the reference group encoding of s
    def expressive_words(self, s: str, words: list[str]) -> int:
        s_groups = self._group(s)

        def stretchy(word: str) -> bool:
            w_groups = self._group(word)
            if len(w_groups) != len(s_groups):
                return False
            return all(
                s_char == w_char and (s_len == w_len or (s_len >= 3 and s_len > w_len))
                for (s_char, s_len), (w_char, w_len) in zip(s_groups, w_groups, strict=True)
            )

        return sum(1 for word in words if stretchy(word))

    def _group(self, text: str) -> list[tuple[str, int]]:
        groups: list[tuple[str, int]] = []
        for char in text:
            if groups and groups[-1][0] == char:
                prev_char, prev_len = groups[-1]
                groups[-1] = (prev_char, prev_len + 1)
            else:
                groups.append((char, 1))
        return groups
```

## Complexity

| Time | Space |
| - | - |
| O(len(s) + sum(len(w) for w in words)) | O(len(s)) for the reference group encoding of s |

## Tags


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.