Expressive Words
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 <= 1001 <= words[i].length <= 100sand 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(n + Σ|w|)Each character of s and of every word is scanned a constant number of times.O(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.
- Encode s into runs.
- For each word: encode it; if the run counts differ in number, skip it.
- For each run k: letters must match; with sc = s count and wc = word count, require sc == wc or (sc >= 3 and sc > wc).
- 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;
}
}class Solution:
def expressiveWords(self, s: str, words: List[str]) -> int:
def runs(t: str) -> List[List]:
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
target = runs(s)
count = 0
for w in words:
cur = runs(w)
if len(cur) != len(target):
continue
ok = True
for (ca, na), (cb, nb) in zip(target, cur):
if ca != cb or (na != nb and (na < 3 or na < nb)):
ok = False
break
if ok:
count += 1
return countclass Solution {
public:
int expressiveWords(string s, vector<string>& words) {
vector<pair<char, int>> target = runs(s);
int count = 0;
for (auto& w : words) {
vector<pair<char, int>> cur = runs(w);
if (cur.size() != target.size()) continue;
bool ok = true;
for (size_t k = 0; k < cur.size() && ok; k++) {
auto a = target[k], b = cur[k];
if (a.first != b.first) ok = false;
else if (a.second != b.second && (a.second < 3 || a.second < b.second)) ok = false;
}
if (ok) count++;
}
return count;
}
private:
vector<pair<char, int>> runs(const string& s) {
vector<pair<char, int>> out;
size_t i = 0;
while (i < s.size()) {
size_t j = i;
while (j < s.size() && s[j] == s[i]) j++;
out.push_back({s[i], (int)(j - i)});
i = j;
}
return out;
}
};function expressiveWords(s, words) {
const runs = (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 target = runs(s);
let count = 0;
for (const w of words) {
const cur = runs(w);
if (cur.length !== target.length) continue;
let ok = true;
for (let k = 0; k < cur.length && ok; k++) {
const [ca, na] = target[k], [cb, nb] = cur[k];
if (ca !== cb) ok = false;
else if (na !== nb && (na < 3 || na < nb)) ok = false;
}
if (ok) count++;
}
return count;
}2Optimal (two pointers per word)
O(Σ(n + |w|))For each word, both strings are scanned once.O(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.
- For each word, i = 0 (in s) and j = 0 (in the word).
- While both are in range: if s[i] != w[j], fail. Measure run lengths sc and wc starting at i and j.
- Fail unless sc == wc or (sc >= 3 and sc > wc). Advance i += sc, j += wc.
- 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();
}
}class Solution:
def expressiveWords(self, s: str, words: List[str]) -> int:
def stretchy(w: str) -> bool:
i = j = 0
while i < len(s) and j < len(w):
if s[i] != w[j]:
return False
c = s[i]
si, wj = i, j
while i < len(s) and s[i] == c:
i += 1
while j < len(w) and w[j] == c:
j += 1
sc, wc = i - si, j - wj
if sc != wc and (sc < 3 or sc < wc):
return False
return i == len(s) and j == len(w)
return sum(1 for w in words if stretchy(w))class Solution {
public:
int expressiveWords(string s, vector<string>& words) {
int count = 0;
for (auto& w : words) if (stretchy(s, w)) count++;
return count;
}
private:
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];
size_t si = i, wj = j;
while (i < s.size() && s[i] == c) i++;
while (j < w.size() && w[j] == c) j++;
int sc = i - si, wc = j - wj;
if (sc != wc && (sc < 3 || sc < wc)) return false;
}
return i == s.size() && j == w.size();
}
};function expressiveWords(s, words) {
const stretchy = (w) => {
let i = 0, j = 0;
while (i < s.length && j < w.length) {
if (s[i] !== w[j]) return false;
const c = s[i];
const si = i, wj = j;
while (i < s.length && s[i] === c) i++;
while (j < w.length && w[j] === c) j++;
const sc = i - si, wc = j - wj;
if (sc !== wc && (sc < 3 || sc < wc)) return false;
}
return i === s.length && j === w.length;
};
let count = 0;
for (const w of words) if (stretchy(w)) count++;
return count;
}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.