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:

"heeellooo"

the groups are:

"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

Examples

Example:

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

The word "hello" can become "heeellooo":

"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:

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:

s = "heeellooo"
word = "hello"

Their groups are:

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:

s_count == word_count

or:

s_count >= 3 and s_count > word_count

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

Algorithm

Define a helper function:

is_stretchy(s, word)

Use two pointers:

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.

Implementation

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:

i = 0
j = 0

They move through s and word.

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

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

We count the current group length in s:

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:

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:

if w_count > s_count:
    return False

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

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

Finally, both strings must end together:

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

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

Testing

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()