LeetCode 809 - Expressive Words

The problem asks us to determine how many words in the words array can be transformed into the target string s using a very specific type of expansion operation.

leetcodemediumarraytwo-pointersstring

LeetCode Problem 809

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, String

Solution

Problem Understanding

The problem asks us to determine how many words in the words array can be transformed into the target string s using a very specific type of expansion operation.

The key concept is that characters in a word can only be expanded if they belong to a group whose final size becomes at least three. A group is a sequence of adjacent identical characters. For example, in the string "heeellooo", the groups are:

  • "h" with length 1
  • "eee" with length 3
  • "ll" with length 2
  • "ooo" with length 3

A word is considered stretchy if we can repeatedly expand some of its groups until it becomes exactly equal to s.

The important restriction is that expansion is only allowed when the resulting group in s has size at least 3. This creates three critical rules:

  • The characters in both strings must appear in the same order.
  • Corresponding groups must contain the same character.
  • If a group in s has length less than 3, then the word must already have exactly the same group length.
  • If a group in s has length at least 3, then the word's group length may be smaller, because it could have been expanded.

The input consists of:

  • A target string s
  • An array words

The output is the number of words that satisfy the stretchy condition.

The constraints are small:

  • Length of s is at most 100
  • Number of words is at most 100
  • Each word length is at most 100

These constraints mean even an O(n * m) style solution is perfectly acceptable, where n is the number of words and m is the string length.

Several edge cases are important:

  • Words with different character ordering can never match.
  • A smaller group in s cannot absorb extra characters.
  • Single-character groups are especially restrictive.
  • Entirely identical strings should count as stretchy.
  • Very short words may fail because they cannot legally expand enough groups.

Approaches

Brute Force Approach

A brute-force strategy would attempt to simulate every possible expansion operation on each word until either:

  • The word becomes equal to s
  • The word becomes too large or impossible to match

This approach is theoretically correct because it explores all valid transformations. However, it quickly becomes impractical because each expandable group can grow in many different ways, creating a large branching search space.

For example, if a word contains several expandable groups, there are many combinations of expansion lengths to test. Even though the constraints are small, exhaustive generation is unnecessary and inefficient.

The important observation is that we do not actually need to simulate expansions. We only need to compare the group structure of the two strings.

Optimal Approach

The optimal solution uses two pointers to scan both strings group by group.

The key insight is that stretchy behavior depends entirely on the lengths of corresponding character groups.

For every group:

  • If the characters differ, the word cannot match.
  • If the group in s is shorter than 3, both groups must have exactly the same size.
  • If the group in s is at least 3, the word's group can be smaller, but not larger.

This allows us to validate a word in a single linear scan.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential Exponential Simulates all possible expansions
Optimal O(W × N) O(1) Compares character groups directly

Here:

  • W is the number of words
  • N is the maximum string length

Algorithm Walkthrough

Optimal Two-Pointer Algorithm

  1. Initialize two pointers, one for s and one for the current word.

These pointers allow us to process both strings from left to right while grouping consecutive identical characters together. 2. At each step, compare the current characters.

If the characters differ, the strings cannot possibly match because expansions never change character order. 3. Count the size of the current character group in both strings.

For example:

  • "eee" has group size 3
  • "ll" has group size 2

We move forward until the character changes. 4. Apply the stretchy rules.

Let:

  • countS be the group length in s
  • countW be the group length in the word

There are two invalid situations:

  • countS < countW

The word already has more characters than s, which cannot be fixed by expansion.

  • countS != countW and countS < 3

If the target group is smaller than 3, expansion is illegal, so lengths must match exactly. 5. Continue processing all groups.

Every group must satisfy the rules for the word to be stretchy. 6. After processing, ensure both strings are fully consumed.

If one string still has remaining characters, the structures differ and the word is invalid. 7. Repeat for every word and count how many succeed.

Why it works

The algorithm works because stretching only affects group sizes, never character order or group sequence.

By comparing corresponding groups directly, we verify exactly whether the smaller word could legally expand into s.

The rules completely characterize all valid transformations:

  • Groups in s smaller than 3 cannot be expanded.
  • Groups in s of size at least 3 may absorb additional repeated characters.

Since every group is checked independently and all groups must match, the algorithm is correct.

Python Solution

from typing import List

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
                
                char_s = s[i]
                count_s = 0
                
                while i < len(s) and s[i] == char_s:
                    i += 1
                    count_s += 1
                
                char_w = word[j]
                count_w = 0
                
                while j < len(word) and word[j] == char_w:
                    j += 1
                    count_w += 1
                
                if count_s < count_w:
                    return False
                
                if count_s != count_w and count_s < 3:
                    return False
            
            return i == len(s) and j == len(word)
        
        stretchy_count = 0
        
        for word in words:
            if is_stretchy(word):
                stretchy_count += 1
        
        return stretchy_count

The implementation defines a helper function is_stretchy that checks whether a single word can expand into s.

Two pointers, i and j, track positions in s and the current word. The code repeatedly extracts matching character groups and counts their lengths.

The first validation condition checks whether the word has more characters in a group than s. This is impossible because expansion only adds characters.

The second validation condition enforces the expansion rule. If the group sizes differ, the target group in s must have size at least 3.

After all groups are processed, both pointers must reach the end of their respective strings. This guarantees that the entire structure matched correctly.

Finally, the main function iterates through every word and counts the valid ones.

Go Solution

func expressiveWords(s string, words []string) int {
    
    isStretchy := func(word string) bool {
        i := 0
        j := 0
        
        for i < len(s) && j < len(word) {
            
            if s[i] != word[j] {
                return false
            }
            
            charS := s[i]
            countS := 0
            
            for i < len(s) && s[i] == charS {
                i++
                countS++
            }
            
            charW := word[j]
            countW := 0
            
            for j < len(word) && word[j] == charW {
                j++
                countW++
            }
            
            if countS < countW {
                return false
            }
            
            if countS != countW && countS < 3 {
                return false
            }
        }
        
        return i == len(s) && j == len(word)
    }
    
    result := 0
    
    for _, word := range words {
        if isStretchy(word) {
            result++
        }
    }
    
    return result
}

The Go implementation follows the same logic as the Python version.

Because Go strings are byte-indexed, direct indexing works safely here since the problem guarantees lowercase English letters only.

The helper function is implemented as a closure inside expressiveWords. Group counting uses simple loops and integer counters.

There are no special overflow concerns because string lengths are very small.

Worked Examples

Example 1

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

We process each word independently.

Word = "hello"

Group s Group Size in s Word Group Size in Word Valid?
1 h 1 h 1 Yes
2 eee 3 e 1 Yes
3 ll 2 ll 2 Yes
4 ooo 3 o 1 Yes

Result: stretchy

Word = "hi"

Group s Group Size in s Word Group Size in Word Valid?
1 h 1 h 1 Yes
2 eee 3 i mismatch No

Result: not stretchy

Word = "helo"

Group s Group Size in s Word Group Size in Word Valid?
1 h 1 h 1 Yes
2 eee 3 e 1 Yes
3 ll 2 l 1 No

The "ll" group in s has size 2, which is less than 3, so the word must also contain exactly 2 l characters.

Result: not stretchy

Final answer: 1

Example 2

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

Word = "zzyy"

Group s Group Size Word Group Size Valid?
z 5 2 Yes
y 5 2 Yes

Stretchy.

Word = "zy"

Group s Group Size Word Group Size Valid?
z 5 1 Yes
y 5 1 Yes

Stretchy.

Word = "zyy"

Group s Group Size Word Group Size Valid?
z 5 1 Yes
y 5 2 Yes

Stretchy.

Final answer: 3

Complexity Analysis

Measure Complexity Explanation
Time O(W × N) Each word is scanned once
Space O(1) Only pointer and counter variables are used

For each word, both pointers move strictly forward through the strings. No character is processed more than once per comparison.

If:

  • W is the number of words
  • N is the maximum string length

then the total runtime is O(W × N).

The algorithm uses constant extra memory because it only stores indices and counters.

Test Cases

from typing import List

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
                
                char_s = s[i]
                count_s = 0
                
                while i < len(s) and s[i] == char_s:
                    i += 1
                    count_s += 1
                
                char_w = word[j]
                count_w = 0
                
                while j < len(word) and word[j] == char_w:
                    j += 1
                    count_w += 1
                
                if count_s < count_w:
                    return False
                
                if count_s != count_w and count_s < 3:
                    return False
            
            return i == len(s) and j == len(word)
        
        return sum(is_stretchy(word) for word in words)

sol = Solution()

assert sol.expressiveWords(
    "heeellooo",
    ["hello", "hi", "helo"]
) == 1  # provided example

assert sol.expressiveWords(
    "zzzzzyyyyy",
    ["zzyy", "zy", "zyy"]
) == 3  # all words are stretchy

assert sol.expressiveWords(
    "abc",
    ["abc"]
) == 1  # identical strings

assert sol.expressiveWords(
    "abc",
    ["ab"]
) == 0  # missing group

assert sol.expressiveWords(
    "aaa",
    ["a"]
) == 1  # expandable group

assert sol.expressiveWords(
    "aa",
    ["a"]
) == 0  # cannot stretch to size 2

assert sol.expressiveWords(
    "abcd",
    ["abcdd"]
) == 0  # word group larger than target

assert sol.expressiveWords(
    "heeellooo",
    ["heeellooo"]
) == 1  # exact match

assert sol.expressiveWords(
    "heeellooo",
    ["helloo"]
) == 0  # target group too small

assert sol.expressiveWords(
    "xxxxx",
    ["x", "xx", "xxx", "xxxx"]
) == 4  # all expandable into size 5

assert sol.expressiveWords(
    "aab",
    ["abb", "aab", "ab"]
) == 1  # only exact match works
Test Why
"heeellooo" with mixed words Validates standard behavior
"zzzzzyyyyy" Validates large expandable groups
"abc" vs "abc" Exact equality case
"abc" vs "ab" Missing characters
"aaa" vs "a" Legal expansion
"aa" vs "a" Illegal expansion because target size < 3
"abcd" vs "abcdd" Word group larger than target
Exact same long string Confirms direct matches work
"helloo" case Non-expandable target group
Repeated single character groups Stress test for expansions
Mixed valid and invalid words Verifies selective counting

Edge Cases

Target Group Size Less Than Three

A very common source of bugs is forgetting that groups of size 1 or 2 in s cannot be expanded.

For example:

s = "ll"
word = "l"

Even though the word only differs by one character, the transformation is illegal because the target group size is only 2. Expansion is only allowed when the resulting group has size at least 3.

The implementation handles this with:

if count_s != count_w and count_s < 3:
    return False

Word Contains More Characters Than Target

Another important edge case occurs when a word already has a larger group than s.

For example:

s = "helo"
word = "helllo"

No operation removes characters, so this can never match.

The implementation correctly rejects such cases using:

if count_s < count_w:
    return False

Different Character Ordering

Stretching never changes character order.

For example:

s = "heeellooo"
word = "heeleloo"

Even if group counts seem similar, the sequence of groups differs, making transformation impossible.

The algorithm immediately detects this using:

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

This guarantees mismatched structures fail early.