Skip to main content
Talentd

Expressive Words - Solution & Explanation

MediumArrayTwo PointersString16 min readAsked at: Cisco, Google
Practice this problem

Problem Statement

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.

  • For example, starting with "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 <= 100
  • 1 <= words[i].length <= 100
  • s and words[i] consist of lowercase letters.

Approach Overview

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 1: Two-Pointer Approach with Grouping

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Regex-Based Matching

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.

Code

C#Java

C#

Java

Complexity

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.

Try this approach in the editor →

Approach 3: Traversal Counting + Two Pointers

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pointer Approach with GroupingO(n + totalWordsLength)O(1)Best general solution. Efficient linear scan with explicit control over character groups.
Regex-Based MatchingO(n + totalWordsLength) averageO(n)Useful when regex support is strong and implementation speed matters more than raw performance.

Video Solution

Leetcode - 809 - Expressive Words • Algo Process • 7,393 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Expressive Words easy or hard?
Expressive Words is considered a medium-level problem. The difficulty comes from correctly handling grouped characters and the rule that only groups of length three or more can stretch. Once the grouping insight is clear, the implementation becomes straightforward.
Expressive Words Python/Java solution
Python and Java solutions typically implement the two-pointer grouping technique. Iterate through both strings, count consecutive characters, and verify the stretching conditions. The same logic also works in JavaScript, C#, and other languages with simple loops.
How to solve Expressive Words in O(n)?
Process character groups instead of individual characters. Use two pointers to walk through the base string and the candidate word while counting consecutive characters. A word matches if each group either has the same length or the base string group has length ≥ 3 and is longer than the word’s group.
What is the best approach for Expressive Words?
The two-pointer grouping approach is the most efficient and commonly expected solution. It compares groups of identical characters in the base string and each word while validating stretch rules. The algorithm runs in O(n + total word length) time and O(1) extra space, making it optimal for interview settings.
Is Expressive Words asked at Google/Amazon/Meta?
Expressive Words appears in coding interview preparation sets for companies like Google and Meta because it tests string processing, group counting, and careful edge-case handling. The problem evaluates whether candidates can design linear-time algorithms using two pointers.
What data structure is used in Expressive Words?
The solution mainly uses two pointers and group counting over strings. No complex data structures are required—just sequential traversal and counters for character groups. This makes it a classic string and two-pointer problem.
What is the time complexity of Expressive Words?
The optimal solution runs in O(n + totalWordsLength) time, where n is the length of the base string and totalWordsLength is the sum of lengths of all words. Each character in both strings is processed at most once when counting character groups. Space complexity is O(1) for the two-pointer approach.

Ready to solve this problem?

Practice Expressive Words with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays