Expressive Words

medium two-pointers strings run-length

Problem

A stretchy word is built by extending some character group to length >= 3. Given s and a list of words, return how many words can be stretched to become s.

Inputs = "heeellooo", words = ["hello"]

Output1

"hello" → "heeellooo" by stretching e and o.

s ; comma-separated words

def expressiveWords(s, words):
    def groups(t):
        out = []
        i = 0
        while i < len(t):
            j = i
            while j < len(t) and t[j] == t[i]: j += 1
            out.append((t[i], j - i))
            i = j
        return out
    sg = groups(s)
    cnt = 0
    for w in words:
        wg = groups(w)
        if len(wg) != len(sg): continue
        ok = True
        for (a, na), (b, nb) in zip(sg, wg):
            if a != b or na < nb or (na != nb and na < 3):
                ok = False; break
        if ok: cnt += 1
    return cnt

var expressiveWords = function(s, words) {
    const groups = (t) => {
        const out = []; let i = 0;
        while (i < t.length) {
            let j = i; while (j < t.length && t[j] === t[i]) j++;
            out.push([t[i], j - i]); i = j;
        }
        return out;
    };
    const sg = groups(s);
    let cnt = 0;
    for (const w of words) {
        const wg = groups(w);
        if (wg.length !== sg.length) continue;
        let ok = true;
        for (let k = 0; k < sg.length; k++) {
            const [a, na] = sg[k], [b, nb] = wg[k];
            if (a !== b || na < nb || (na !== nb && na < 3)) { ok = false; break; }
        }
        if (ok) cnt++;
    }
    return cnt;
};

class Solution {
    public int expressiveWords(String s, String[] words) {
        int[][] sg = groups(s);
        int cnt = 0;
        for (String w : words) {
            int[][] wg = groups(w);
            if (wg.length != sg.length) continue;
            boolean ok = true;
            for (int k = 0; k < sg.length; k++) {
                if (sg[k][0] != wg[k][0] || sg[k][1] < wg[k][1] || (sg[k][1] != wg[k][1] && sg[k][1] < 3)) { ok = false; break; }
            }
            if (ok) cnt++;
        }
        return cnt;
    }
    private int[][] groups(String t) {
        java.util.List<int[]> out = new java.util.ArrayList<>();
        int i = 0;
        while (i < t.length()) {
            int j = i;
            while (j < t.length() && t.charAt(j) == t.charAt(i)) j++;
            out.add(new int[]{t.charAt(i), j - i});
            i = j;
        }
        return out.toArray(new int[0][]);
    }
}

class Solution {
    vector<pair<char,int>> groups(const string& t) {
        vector<pair<char,int>> out;
        int i = 0;
        while (i < (int)t.size()) {
            int j = i;
            while (j < (int)t.size() && t[j] == t[i]) j++;
            out.push_back({t[i], j - i});
            i = j;
        }
        return out;
    }
public:
    int expressiveWords(string s, vector<string>& words) {
        auto sg = groups(s);
        int cnt = 0;
        for (auto& w : words) {
            auto wg = groups(w);
            if (wg.size() != sg.size()) continue;
            bool ok = true;
            for (int k = 0; k < (int)sg.size(); k++) {
                if (sg[k].first != wg[k].first || sg[k].second < wg[k].second || (sg[k].second != wg[k].second && sg[k].second < 3)) { ok = false; break; }
            }
            if (ok) cnt++;
        }
        return cnt;
    }
};

Explanation

A word can be "stretched" into s only if they have the same letters in the same order, where some runs of a letter were repeated. The trick is to compare them as run-length groups: turn each string into a list of (character, count) pairs.

The helper groups(t) walks the string and bundles each block of identical letters into one pair. For example "heeellooo" becomes h×1, e×3, l×2, o×3 and "hello" becomes h×1, e×1, l×2, o×1.

For a word to match, it must have the same number of groups in the same letter order. Then for each group we check the stretch rule: the letters must match, the word's count nb cannot exceed s's count na, and if the counts differ the stretched count must be at least 3 (you can only extend a group to length 3 or more).

Walking the groups together: h 1 vs 1 (equal, OK), e 3 vs 1 (3 ≥ 1 and 3 ≥ 3, OK), l 2 vs 2 (equal, OK), o 3 vs 1 (OK). Every group passes, so "hello" counts.

If any group fails, the word is rejected. We tally how many words pass and return that count.

Time: O(N * L) Space: O(L)