Expressive Words

Medium Arrays & Hashing Two Pointer Original on LeetCode

Expressive Words is a medium arrays & hashing problem solved with the two pointer pattern. The best approach, optimal (two pointers per word), runs in O(Σ(n + |w|)) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (run-length encode every word) up.

Problem

Some people stretch letters for emphasis, writing "sooo" instead of "so". A run is a maximal block of equal adjacent letters. A word can be stretched by choosing a run and adding more copies of its letter, but only if that run ends up with at least 3 letters. You may stretch any number of runs (or none).

Given a target string s and a list of words, return how many words can be stretched into exactly s.

Examples

Example 1

Input
s = "beeeepp", words = ["bep", "beep", "bepp", "beeepp", "bp"]
Output
2
Why
"bepp" and "beeepp" work: the e-run grows to 4, which is allowed because the result has at least 3 letters. The others would need the p-run to grow from 1 to 2, which is too short, or are missing a run.

Example 2

Input
s = "aaa", words = ["a", "aa", "aaa", "aaaa"]
Output
3
Why
A run can grow to 3 but never shrink, so "aaaa" fails.

Example 3

Input
s = "xyz", words = ["xyz", "xyyz", "xz"]
Output
1
Why
Only the identical word matches; runs in s are length 1 and cannot come from stretching.

Constraints

  • 1 <= s.length, words.length <= 100
  • 1 <= words[i].length <= 100
  • s and every word contain only lowercase English letters.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (run-length encode every word)O(n + Σ|w|)O(n + max|w|)
Optimal (two pointers per word)O(Σ(n + |w|))O(1)

1Brute force (run-length encode every word)

TimeO(n + Σ|w|)Each character of s and of every word is scanned a constant number of times.
SpaceO(n + max|w|)The run lists for s and the current word.

Encode s once as a list of (letter, count) runs. For each word, encode it the same way and compare the two lists run by run with the stretch rule.

  1. Encode s into runs.
  2. For each word: encode it; if the run counts differ in number, skip it.
  3. For each run k: letters must match; with sc = s count and wc = word count, require sc == wc or (sc >= 3 and sc > wc).
  4. Count the words where every run passes.
class Solution {
    public int expressiveWords(String s, String[] words) {
        List<int[]> target = runs(s);
        int count = 0;
        for (String w : words) {
            List<int[]> cur = runs(w);
            if (cur.size() != target.size()) continue;
            boolean ok = true;
            for (int k = 0; k < cur.size() && ok; k++) {
                int[] a = target.get(k), b = cur.get(k);
                if (a[0] != b[0]) ok = false;
                else if (a[1] != b[1] && (a[1] < 3 || a[1] < b[1])) ok = false;
            }
            if (ok) count++;
        }
        return count;
    }

    private List<int[]> runs(String s) {
        List<int[]> out = new ArrayList<>();
        int i = 0;
        while (i < s.length()) {
            int j = i;
            while (j < s.length() && s.charAt(j) == s.charAt(i)) j++;
            out.add(new int[] { s.charAt(i), j - i });
            i = j;
        }
        return out;
    }
}

2Optimal (two pointers per word)

TimeO(Σ(n + |w|))For each word, both strings are scanned once.
SpaceO(1)Only indices and counters.

Walk s and the word together. At each step both indices sit at the start of a run; measure the run length in each string from there, check the letters and the stretch rule, then jump both indices past their runs. The word matches if both reach the end together.

  1. For each word, i = 0 (in s) and j = 0 (in the word).
  2. While both are in range: if s[i] != w[j], fail. Measure run lengths sc and wc starting at i and j.
  3. Fail unless sc == wc or (sc >= 3 and sc > wc). Advance i += sc, j += wc.
  4. The word counts if i == s.length and j == w.length.
class Solution {
    public int expressiveWords(String s, String[] words) {
        int count = 0;
        for (String w : words) if (stretchy(s, w)) count++;
        return count;
    }

    private 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 si = i, wj = j;
            while (i < s.length() && s.charAt(i) == c) i++;
            while (j < w.length() && w.charAt(j) == c) j++;
            int sc = i - si, wc = j - wj;
            if (sc != wc && (sc < 3 || sc < wc)) return false;
        }
        return i == s.length() && j == w.length();
    }
}

Edge cases to test

  • A word identical to s
  • A run in the word longer than the run in s (never allowed)
  • A run in s of length exactly 2 that differs from the word's run (not allowed: stretched runs must reach 3)
  • Different number of runs or different letters

Hints

Hint 1

Think of both strings as runs of equal letters: beeeepp is b×1, e×4, p×2.

Hint 2

Compare runs pairwise. With counts c in s and w in the word, the run is fine if c == w, or if c >= 3 and c > w.

Hint 3

You can compare the runs on the fly with one index in each string, without storing them.

FAQ

What is the best time complexity for Expressive Words?

Optimal (two pointers per word) runs in O(Σ(n + |w|)) time and O(1) extra space. For each word, both strings are scanned once.

Which pattern does Expressive Words use?

It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.

Is there a brute force solution for Expressive Words?

Yes. Brute force (run-length encode every word) takes O(n + Σ|w|) time and O(n + max|w|) space. Encode s once as a list of (letter, count) runs.

Which edge cases should I test for Expressive Words?

A word identical to s; A run in the word longer than the run in s (never allowed); A run in s of length exactly 2 that differs from the word's run (not allowed: stretched runs must reach 3); Different number of runs or different letters.