Watch 10 video solutions for Expressive Words, a medium level problem involving Array, Two Pointers, String. This walkthrough by Algo Process has 7,293 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Sometimes people repeat letters to represent extra feeling. For example:
"hello" -> "heeellooo""hi" -> "hiiii"In these strings like "heeellooo", we have groups of adjacent letters that are all the same: "h", "eee", "ll", "ooo".
You are given a string s and an array of query strings words. A query word is stretchy if it can be made to be equal to s by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is three or more.
"hello", we could do an extension on the group "o" to get "hellooo", but we cannot get "helloo" since the group "oo" has a size less than three. Also, we could do another extension like "ll" -> "lllll" to get "helllllooo". If s = "helllllooo", then the query word "hello" would be stretchy because of these two extension operations: query = "hello" -> "hellooo" -> "helllllooo" = s.Return the number of query strings that are stretchy.
Example 1:
Input: s = "heeellooo", words = ["hello", "hi", "helo"] Output: 1 Explanation: We can extend "e" and "o" in the word "hello" to get "heeellooo". We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more.
Example 2:
Input: s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"] Output: 3
Constraints:
1 <= s.length, words.length <= 1001 <= words[i].length <= 100s and words[i] consist of lowercase letters.Problem Overview: You get a base string s and a list of words. A word is considered expressive if you can stretch some character groups in the word so it becomes exactly s. Stretching means repeating characters in a group to length ≥ 3 without changing the character order. The task is to count how many words can transform into s.
Approach 1: Two-Pointer Approach with Grouping (O(n + totalWordsLength) time, O(1) space)
This approach scans both strings using two pointers. The idea is to compare groups of the same character instead of individual characters. Move pointers through s and the candidate word, count the length of each consecutive group (for example "eee" vs "e"). If the characters differ, the word cannot match. If the counts are equal, the group matches directly. If the count in s is ≥ 3 and larger than the word's group, stretching is allowed. Otherwise the word is invalid. This method processes each character once, making it efficient for large inputs and a natural fit for problems involving grouped characters in string processing.
The key insight: only groups with length ≥ 3 in s can absorb extra characters. Smaller groups must match exactly. Iterating with grouped counts avoids unnecessary comparisons and keeps the algorithm linear.
Approach 2: Regex-Based Matching (O(n + totalWordsLength) average time, O(n) space)
Another option converts s into a flexible regular expression. Each character group in s becomes a regex pattern: groups with length ≥ 3 allow a range like e{1,3} or more flexible repetition, while shorter groups require exact counts. After building the regex pattern, test every word using a regex match. This approach leverages the built-in regex engine instead of manually implementing group comparisons.
The regex method is concise and expressive but introduces overhead from pattern compilation and matching. Regex engines also hide the internal complexity, which may lead to slower performance compared to a direct algorithm. It’s still a practical solution when readability is preferred or when working in languages with strong regex support.
Recommended for interviews: The two-pointer grouping solution is what interviewers usually expect. It demonstrates control over array-style traversal, careful handling of character groups, and linear-time reasoning. The regex approach shows creativity but relies on library behavior rather than algorithm design. Showing the grouping idea first and implementing it with two pointers signals strong problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pointer Approach with Grouping | O(n + totalWordsLength) | O(1) | Best general solution. Efficient linear scan with explicit control over character groups. |
| Regex-Based Matching | O(n + totalWordsLength) average | O(n) | Useful when regex support is strong and implementation speed matters more than raw performance. |