Expressive Words Solution for Google
Company: Google · Difficulty: Medium · Topics: String, Two Pointers
Problem Statement
Sometimes people repeat letters to represent extra feeling, such as "hello" -> "heeellooo", "hi" -> "hiiii". In these strings like "heeellooo", we have groups of adjacent letters that are all the same: "h", "eee", "ll", "ooo".
For some given string s, 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 3 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 size 2, which is less than 3. Also, we could do another kind of extension on the group "l" to get "helllllooo", but we cannot get "helllloo" since the group "ll" has size 2, which is less than 3.
Given two strings s and words, return the number of words in words that are stretchy to s.
Examples
Example 1:
Input: s = "heeellooo", words = ["hello", "hi", "helo"]
Output: 1
Explanation:
- "hello" can be stretched to "heeellooo" by extending "e" and "o"
- "hi" cannot be stretched to "heeellooo"
- "helo" cannot be stretched to "heeellooo"
Example 2:
Input: s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"]
Output: 3
Explanation:
- All three words can be stretched to "zzzzzyyyyy"
Intuition
The key insight is to compare groups of consecutive identical characters between the target string and each word. A word is stretchy if:
1. It has the same sequence of characters as the target
2. Each group in the word can be extended to match the corresponding group in the target
3. Extensions are only allowed if the target group has 3 or more characters
Approach
1. Group Comparison: For each word, compare it character by character with the target string
2. Group Counting: Count consecutive identical characters in both strings
3. Stretchability Check: A group is stretchable if:
- The characters match
- Either both groups have the same length, or the target group has 3+ characters and is longer
4. Two Pointers: Use two pointers to traverse both strings simultaneously
Solution
⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.
Solution: Two Pointers with Group Comparison
Time Complexity: O(n * m) - Where n is the number of words and m is the average word length
Space Complexity: O(1) - Constant extra space