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 <= 1001 <= words[i].length <= 100s and words[i] consist of lowercase English letters
Hints for Expressive Words
Hint 1
Compare
sand a word group by group: the letters of the groups must agree one for one.Hint 2
For a group of length
ainsandbin the word: equal lengths are fine; otherwise the word's group must be shorter and the stretched one must reach 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
- For each word, keep pointers
iintosandjinto the word. - While both are inside their strings: if
s[i] != word[j]the word fails; otherwise count the run lengthaof that letter insandbin the word, advancing both pointers past their runs. - The group is fine if
a == b, or ifa >= 3anda > b; otherwise the word fails. - 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
scan only match a group of length exactly 2 — stretching must reach at least 3. - A word's group longer than the matching group of
sfails; 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.