Expressive Words

Medium
1207.

Expressive Words

Expressive Words is a medium coding problem on arrays, strings and two pointers, asked in Amazon and Google interviews.

People stretch words for emphasis: "hello" becomes "heeellooo". A group is a maximal run of the same letter, so "heeellooo" has the groups h, eee, ll, ooo.

A word can be stretched into s when s is obtained by repeatedly choosing a group of the word and adding copies of its letter, so that the group ends up with at least 3 letters. A group may also be left as it is.

Given s and a list of query words, return how many of the words can be stretched into s.

Example 1

Input
s = "kaaaiirooo", words = ["kairo","kaiiro","kaaiirooo","kair"]
Output
2
Explanation
`kaiiro` and `kaaiirooo` work. `kairo` would need its `i` group grown to exactly 2, which is not allowed; `kair` has no `o` group.

Example 2

Input
s = "zzzyyy", words = ["zy","zzy","zyyyy"]
Output
2
Explanation
`zyyyy` has four `y`s, more than `s` has.

Example 3

Input
s = "abc", words = ["abc","ab","abcc"]
Output
1

Constraints

  • 1 <= s.length, words.length <= 100
  • 1 <= words[i].length <= 100
  • s and words[i] consist of lowercase English letters
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string[]} words
 * @return {number}
 */
var expressiveWords = function(s, words) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Expressive Words — Solution in Python, Java & C++

Expressive Words solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and strings.

Expressive Words is a medium coding problem on arrays, strings and two pointers, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Strings, Two Pointers
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

People stretch words for emphasis: "hello" becomes "heeellooo". A group is a maximal run of the same letter, so "heeellooo" has the groups h, eee, ll, ooo.

A word can be stretched into s when s is obtained by repeatedly choosing a group of the word and adding copies of its letter, so that the group ends up with at least 3 letters. A group may also be left as it is.

Given s and a list of query words, return how many of the words can be stretched into s.

Example 1

Input: s = "kaaaiirooo", words = ["kairo","kaiiro","kaaiirooo","kair"]
Output: 2
Explanation: `kaiiro` and `kaaiirooo` work. `kairo` would need its `i` group grown to exactly 2, which is not allowed; `kair` has no `o` group.

Example 2

Input: s = "zzzyyy", words = ["zy","zzy","zyyyy"]
Output: 2
Explanation: `zyyyy` has four `y`s, more than `s` has.

Example 3

Input: s = "abc", words = ["abc","ab","abcc"]
Output: 1

Constraints

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

Hints for Expressive Words

  1. Hint 1

    Compare s and a word group by group: the letters of the groups must agree one for one.

  2. Hint 2

    For a group of length a in s and b in the word: equal lengths are fine; otherwise the word's group must be shorter and the stretched one must reach 3.

  3. Hint 3

    Walk both strings with two pointers, measuring each group's length as you go.

How to solve Expressive Words

Stretching never changes the sequence of group letters, only group lengths, so a word works exactly when its groups line up with those of s and each length change is a legal stretch.

Approach

  1. For each word, keep pointers i into s and j into the word.
  2. While both are inside their strings: if s[i] != word[j] the word fails; otherwise count the run length a of that letter in s and b in the word, advancing both pointers past their runs.
  3. The group is fine if a == b, or if a >= 3 and a > b; otherwise the word fails.
  4. The word succeeds if both pointers reach their ends together. Count the successes.

Why it works

Each stretch operation turns one group of length b into length a ≥ 3 with a > b, and leaves every other group alone; groups never merge or split because only copies of the same letter are added. So s is reachable exactly when the group letters match in order and every group either keeps its length or grows to at least 3 — which is what the check tests.

Complexity

  • Time — O(|s| · |words| + total length of the words)
  • Space — O(1)

Pitfalls

  • A group of length 2 in s can only match a group of length exactly 2 — stretching must reach at least 3.
  • A word's group longer than the matching group of s fails; letters are never removed.
  • Check that both strings are fully consumed; an extra trailing group on either side fails.

Reference solution

Python

from typing import List

def expressiveWords(s: str, words: List[str]) -> int:
    def stretchy(w):
        i = j = 0
        while i < len(s) and j < len(w):
            if s[i] != w[j]:
                return False
            c = s[i]
            a = b = 0
            while i < len(s) and s[i] == c:
                i += 1
                a += 1
            while j < len(w) and w[j] == c:
                j += 1
                b += 1
            if a < b or (a != b and a < 3):
                return False
        return i == len(s) and j == len(w)

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

Java

public static int expressiveWords(String s, String[] words) {
    int count = 0;
    for (String w : words) if (stretchy(s, w)) count++;
    return count;
}

static boolean stretchy(String s, String w) {
    int i = 0, j = 0;
    while (i < s.length() && j < w.length()) {
        if (s.charAt(i) != w.charAt(j)) return false;
        char c = s.charAt(i);
        int a = 0, b = 0;
        while (i < s.length() && s.charAt(i) == c) { i++; a++; }
        while (j < w.length() && w.charAt(j) == c) { j++; b++; }
        if (a < b || (a != b && a < 3)) return false;
    }
    return i == s.length() && j == w.length();
}

C++

bool stretchy(const string& s, const string& w) {
    size_t i = 0, j = 0;
    while (i < s.size() && j < w.size()) {
        if (s[i] != w[j]) return false;
        char c = s[i];
        int a = 0, b = 0;
        while (i < s.size() && s[i] == c) { i++; a++; }
        while (j < w.size() && w[j] == c) { j++; b++; }
        if (a < b || (a != b && a < 3)) return false;
    }
    return i == s.size() && j == w.size();
}

int expressiveWords(string s, vector<string>& words) {
    int count = 0;
    for (const string& w : words) if (stretchy(s, w)) count++;
    return count;
}

JavaScript

var expressiveWords = function(s, words) {
    var stretchy = function(w) {
        var i = 0, j = 0;
        while (i < s.length && j < w.length) {
            if (s[i] !== w[j]) return false;
            var c = s[i], a = 0, b = 0;
            while (i < s.length && s[i] === c) { i++; a++; }
            while (j < w.length && w[j] === c) { j++; b++; }
            if (a < b || (a !== b && a < 3)) return false;
        }
        return i === s.length && j === w.length;
    };
    var count = 0;
    for (var k = 0; k < words.length; k++) if (stretchy(words[k])) count++;
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings