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.
This approach involves breaking down the target string 's' and each candidate word into groups of consecutive same characters. We then compare these groups using two pointers, ensuring that a word can be stretched to match 's' by checking the compatibility of their respective character groups.
The Python solution defines a helper function, get_char_groups, to break a word into groups of consecutive identical characters. The function returns a list of tuples, each containing a character and its count. A second helper function, is_stretchy, compares the character groups of 's' and a word. This function checks if each group of 's' can be formed by stretching the word's corresponding group, ensuring the conditions of stretchy transformations are adhered to. For each word in words, the solution compares it with 's' and increments the count of stretchy words if the conditions are met.
Python
JavaScript
Time Complexity: O(N * M), where N is the length of the string 's' and M is the total length of all words combined. Space Complexity: O(N + M) for the storage of character groups.
This approach leverages regular expressions to match the pattern of the original word 's' with each word. By converting 's' into a regex pattern, we can efficiently determine if a word can be transformed into 's'.
The C# solution creates a regex pattern based on the string 's'. It checks if each word can be matched against this pattern using a regular expression. The GetPattern function constructs a regex pattern where each group of characters in 's' (that can be stretched) is represented with quantifiers. The pattern is used to determine if words can match (become) 's' through extensions.
Time Complexity: O(N + L*W), where L is the max length of a word and W is the number of words. Space Complexity: O(N) for the regex pattern.
We can traverse the array words, and for each word t in the array, check if t can be expanded to obtain s. If it can, increment the answer by one.
Therefore, the key problem is to determine if the word t can be expanded to obtain s. We use a function check(s, t) to determine this. The implementation logic of the function is as follows:
First, check the length relationship between s and t. If the length of t is greater than s, return false directly. Otherwise, use two pointers i and j to point to s and t, respectively, both initially set to 0.
If the characters pointed to by i and j are different, then t cannot be expanded to obtain s, and we return false. Otherwise, we need to check the relationship between the consecutive occurrence counts of the characters pointed to by i and j, denoted as c_1 and c_2. If c_1 \lt c_2 or c_1 \lt 3 and c_1 neq c_2, then t cannot be expanded to obtain s, and we return false. Otherwise, move i and j to the right by c_1 and c_2 times, respectively, and continue checking.
If both i and j reach the end of the strings, then t can be expanded to obtain s, and we return true. Otherwise, we return false.
The time complexity is O(n times m + sum_{i=0}^{m-1} w_i), where n and m are the lengths of the string s and the array words, respectively, and w_i is the length of the i-th word in the array words.
| Approach | Complexity |
|---|---|
| Two-Pointer Approach with Grouping | Time Complexity: O(N * M), where N is the length of the string 's' and M is the total length of all words combined. Space Complexity: O(N + M) for the storage of character groups. |
| Regex-Based Matching | Time Complexity: O(N + L*W), where L is the max length of a word and W is the number of words. Space Complexity: O(N) for the regex pattern. |
| Traversal Counting + Two Pointers | — |
| 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. |
Leetcode - 809 - Expressive Words • Algo Process • 7,293 views views
Watch 9 more video solutions →Practice Expressive Words with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor