Stretchy Words (LC 809)

Problem Statement

A word is stretchy if it can be turned into a given query by "stretching" groups of adjacent equal characters. You can stretch a group of length k to any length ≥ max(k, 3).

Given a string s and an array of query words, return the number of query words that are stretchy.

Example 1:

Input:  s = "heeellooo", words = ["hello", "hi", "helo"]
Output: 1
Explanation: "hello" stretches to "heeellooo" (ee->eee valid because eee>=3, and oo->ooo valid).
             "hi" doesn't have the right letters at all.
             "helo" has 'l' once but s has 'll' (size 2). Stretchy rule requires the target group to have size >= max(source, 3); source 1, target 2, but 2 < 3.

Example 2:

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

Constraints:

• 1 <= s.length, words[i].length <= 100
• 1 <= words.length <= 100
• lowercase letters only.

Difficulty: Medium

---

Pattern Recognition

• Input structure: a reference string s and candidate words.
• What are we checking? for each word, whether it can be "stretched" to s under group-size rules.
• Pattern: two-pointer run-length comparison — walk both strings group by group.
• Why: stretching only changes group lengths, not letters or their order. Comparing run-length encodings (RLE) directly answers the question.

This problem is a frequent Google "easy medium" because it tests whether you recognize RLE and execute clean two-pointer logic.

---

Approach

Brute Force

Regenerate all possible stretches of word and check membership — intractable (exponential).

Optimal — Two-Pointer RLE Walk

Key Insight: Walk both strings with pointers i (in s) and j (in word). At each step, read the current run (letter + length) from each. The run is stretchy if and only if:

1. Letters match.
2. Word's run length ≤ s's run length, AND either (a) lengths are equal, or (b) s's run length ≥ 3.

function isStretchy(word, s):
    i = j = 0
    while i < len(s) and j < len(word):
        if s[i] != word[j]: return false
        runS = length of equal-letter run starting at s[i]
        runW = length of equal-letter run starting at word[j]
        if runW > runS: return false
        if runW != runS and runS < 3: return false
        i += runS
        j += runW
    return i == len(s) and j == len(word)

Time: O(|s| + |word|) per word, O(W * (|s| + |w|)) total. Space: O(1).

---

Walkthrough

s = "heeellooo", word = "hello".

i	j	s[i]	word[j]	runS	runW	Decision
0	0	h	h	1	1	equal, advance
1	1	e	e	3	2	runW ≤ runS ✓; runS=3 ≥ 3 so stretch ok; advance
4	2	l	l	2	2	equal, advance
6	3	o	o	3	1	runW ≤ runS ✓; runS=3 ≥ 3 so stretch ok; advance
9	5	end	end	—	—	both exhausted → true

word = "helo":

i	j	s[i]	word[j]	runS	runW	Decision
0	0	h	h	1	1	advance
1	1	e	e	3	1	stretch 1→3: ok (runS ≥ 3). advance
4	2	l	l	2	1	runW=1 ≤ runS=2 ✓; lengths differ and runS=2 < 3 → false

Correct rejection.

---

Implementation

TypeScript

function expressiveWords(s: string, words: string[]): number {
    const runLength = (str: string, idx: number): number => {
        let k = idx;
        while (k < str.length && str[k] === str[idx]) k++;
        return k - idx;
    };

    const isStretchy = (word: string): boolean => {
        let i = 0, j = 0;
        while (i < s.length && j < word.length) {
            if (s[i] !== word[j]) return false;
            const runS = runLength(s, i);
            const runW = runLength(word, j);
            if (runW > runS) return false;
            if (runW !== runS && runS < 3) return false;
            i += runS;
            j += runW;
        }
        return i === s.length && j === word.length;
    };

    let count = 0;
    for (const w of words) if (isStretchy(w)) count++;
    return count;
}

C++

class Solution {
    int runLength(const string& str, int idx) {
        int k = idx;
        while (k < (int)str.size() && str[k] == str[idx]) k++;
        return k - idx;
    }
    bool isStretchy(const string& s, const string& word) {
        int i = 0, j = 0;
        while (i < (int)s.size() && j < (int)word.size()) {
            if (s[i] != word[j]) return false;
            int runS = runLength(s, i);
            int runW = runLength(word, j);
            if (runW > runS) return false;
            if (runW != runS && runS < 3) return false;
            i += runS;
            j += runW;
        }
        return i == (int)s.size() && j == (int)word.size();
    }
public:
    int expressiveWords(string s, vector<string>& words) {
        int count = 0;
        for (auto& w : words) if (isStretchy(s, w)) count++;
        return count;
    }
};

Watch out:

1. Forgetting the "must match at the end" condition (i == len(s) && j == len(word)) lets strings match as prefixes.
2. Off-by-one in the inner run-length loop is a common bug. Double-check by tracing on "aaa".
3. The runS < 3 rule is only applied when runW != runS. If they are equal, you don't care about 3 — it's natural alignment.

---

Complexity Analysis

	Time	Space
Brute Force (enumerate stretches)	exponential	—
Two-Pointer RLE	O(|s| + Σ |word|)	O(1)

Bottleneck: you touch every character in s and each word exactly once. That's optimal.

---

Edge Cases

1. word longer than s — immediate false.
2. word == s — all runs match; return true.
3. Run in word larger than in s — return false (cannot compress).
4. Run of size 2 in s, 1 in word — false; stretching requires target ≥ 3.
5. Run of size 3 in s, 1 in word — true; 3 is the threshold.
6. Different letters early — first check fails.
7. Empty word — return true iff s is also empty; your bounds handle this implicitly.

---

Related Problems

• LC 443 — String Compression — In-place RLE; same pattern, different operation.
• LC 1446 — Consecutive Characters — Simple RLE max-run computation.
• LC 38 — Count and Say — RLE applied recursively.
• LC 791 — Custom Sort String — Character-frequency walking, different objective.

---

What Is Expected at Each Level

Junior: Recognize that you should compare run lengths. May need help formalizing the "≥ max(k, 3)" rule.

Mid-level: Implement cleanly, handle the "lengths differ but s-run < 3" edge case without prompting, state O(|s| + |word|) complexity.

Senior (L4 target): Write the solution quickly, discuss pre-computing RLE of s once vs recomputing per word (matters if words is huge), and note that this is the same "walk two sequences" skeleton underlying LC 443, LC 38, and even diff algorithms. Comment on cache-friendliness of inlining the run loops.