Problem Description

This problem is about identifying "stretchy" words that can be transformed into a target string through character repetition.

Given a string s that represents an "expressive" word (where letters may be repeated for emphasis), and an array of query strings words, you need to determine how many words from the array can be "stretched" to match s.

A word is considered stretchy if it can be transformed into s by applying extension operations. An extension operation works as follows:

• Choose a group of consecutive identical characters c in the word
• Add more characters c to that group so the final group size is at least 3

For example:

• Starting with "hello", you can extend the group "o" to get "hellooo" (group size becomes 3)
• You cannot get "helloo" because the group "oo" has size 2, which is less than 3
• You can also extend "ll" to "lllll" to get "helllllooo"

The key rules for a word to be stretchy:

1. Each character group in the original word must match the corresponding character group in s
2. If a character group in s has 3 or more characters, the corresponding group in the word can have fewer characters (as it can be extended)
3. If a character group in s has less than 3 characters, the corresponding group in the word must have exactly the same count
4. A word cannot have more character groups or different characters than s

The task is to count how many words from the words array are stretchy (can be transformed into s).

Intuition

The key insight is that we need to compare character groups between the target string s and each query word. When we look at strings like "heeellooo" and "hello", we can see they're made up of groups of consecutive identical characters.

For "heeellooo": ["h", "eee", "ll", "ooo"] For "hello": ["h", "e", "ll", "o"]

The fundamental question is: can we extend the groups in the query word to match the groups in s?

This leads us to think about the rules for valid extensions:

• We can only add characters to a group, never remove them
• We can only extend a group to size 3 or more

From these constraints, we can derive the matching conditions between groups:

1. If the target group in s has count c1 and the query group has count c2, then c1 must be >= c2 (we can't remove characters)
2. If c1 >= 3, then any c2 <= c1 works (the group is already extended or can be extended)
3. If c1 < 3, then c1 must equal c2 exactly (we can't extend a group to less than 3)

This naturally suggests a two-pointer approach where we:

• Move through both strings simultaneously
• Count consecutive identical characters in both strings
• Check if the counts satisfy our extension rules
• Continue until we've processed both strings completely

The solution becomes a matter of implementing this group-by-group comparison, ensuring that every group in the query word has a valid corresponding group in s, and that we've consumed both strings entirely (no extra characters in either string).

Learn more about Two Pointers patterns.

Solution Approach

The solution uses a two-pointer technique to compare character groups between the target string s and each query word t. Here's how the implementation works:

Main Function Structure: The main function iterates through each word in the words array and uses a helper function check(s, t) to determine if word t can be stretched to match s. It counts how many words return true.

The check Function Implementation:

1. Initial Length Check:

   • First, compare lengths: if len(t) > len(s), return false immediately
   • This is because we can only add characters, never remove them

2. Two-Pointer Traversal:

   • Initialize pointers i = 0 for string s and j = 0 for string t
   • Continue while both pointers are within bounds

3. Character Matching:

   • At each position, check if s[i] != t[j]
   • If characters don't match, return false (different characters can't be made equal through stretching)

4. Count Consecutive Characters:

   • For string s: Count consecutive occurrences of s[i] starting from position i, store as c1
   • For string t: Count consecutive occurrences of t[j] starting from position j, store as c2
   • Move pointers i and j forward by c1 and c2 respectively

5. Validate Group Counts: Apply the stretching rules:

   • If c1 < c2: Return false (can't remove characters)
   • If c1 < 3 and c1 != c2: Return false (groups with less than 3 characters must match exactly)
   • Otherwise, the group is valid (either c1 >= 3 allowing stretching, or c1 == c2 for exact match)

6. Final Verification:

   • After the loop, check if both i == len(s) and j == len(t)
   • This ensures both strings were fully consumed with no leftover characters

Time Complexity: O(n * m) where n is the length of the words array and m is the average length of strings.

Space Complexity: O(1) as we only use a constant amount of extra space for pointers and counters.

The algorithm efficiently checks each word by comparing groups of characters rather than individual characters, making it well-suited for this stretching problem.

Example Walkthrough

Let's walk through how the algorithm checks if "hello" can be stretched to match "heeellooo".

Target string s = "heeellooo"
Query word t = "hello"

Step 1: Initialize pointers

• i = 0 (pointing to s[0] = 'h')
• j = 0 (pointing to t[0] = 'h')

Step 2: First group comparison - 'h'

• Characters match: s[0] = 'h' and t[0] = 'h' ✓
• Count consecutive 'h' in s: c1 = 1 (just one 'h')
• Count consecutive 'h' in t: c2 = 1 (just one 'h')
• Check rules:
  • c1 >= c2? Yes (1 >= 1) ✓
  • Since c1 < 3 (1 < 3), we need c1 == c2. Yes (1 == 1) ✓
• Move pointers: i = 1, j = 1

Step 3: Second group comparison - 'e'

• Characters match: s[1] = 'e' and t[1] = 'e' ✓
• Count consecutive 'e' in s: c1 = 3 (positions 1,2,3: "eee")
• Count consecutive 'e' in t: c2 = 1 (just one 'e')
• Check rules:
  • c1 >= c2? Yes (3 >= 1) ✓
  • Since c1 >= 3, we can stretch from 1 to 3 ✓
• Move pointers: i = 4, j = 2

Step 4: Third group comparison - 'l'

• Characters match: s[4] = 'l' and t[2] = 'l' ✓
• Count consecutive 'l' in s: c1 = 2 (positions 4,5: "ll")
• Count consecutive 'l' in t: c2 = 2 (positions 2,3: "ll")
• Check rules:
  • c1 >= c2? Yes (2 >= 2) ✓
  • Since c1 < 3 (2 < 3), we need c1 == c2. Yes (2 == 2) ✓
• Move pointers: i = 6, j = 4

Step 5: Fourth group comparison - 'o'

• Characters match: s[6] = 'o' and t[4] = 'o' ✓
• Count consecutive 'o' in s: c1 = 3 (positions 6,7,8: "ooo")
• Count consecutive 'o' in t: c2 = 1 (just one 'o')
• Check rules:
  • c1 >= c2? Yes (3 >= 1) ✓
  • Since c1 >= 3, we can stretch from 1 to 3 ✓
• Move pointers: i = 9, j = 5

Step 6: Final verification

• i == len(s)? Yes (9 == 9) ✓
• j == len(t)? Yes (5 == 5) ✓
• Both strings fully consumed!

Result: "hello" CAN be stretched to "heeellooo"

The word is stretchy because:

• Group 'e' was extended from 1 to 3 characters
• Group 'o' was extended from 1 to 3 characters
• Groups 'h' and 'll' remained unchanged (they had less than 3 characters in the target)

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n + m × w̄) where n is the length of string s, m is the number of words in the words array, and w̄ is the average length of words in the array. This can also be expressed as O(m × n + Σᵢ₌₀^(m-1) wᵢ) where wᵢ is the length of the i-th word.

• The outer loop iterates through all m words in the array
• For each word, the check function is called which performs a two-pointer traversal
• In the check function, we traverse through string s (length n) and word t (length wᵢ) simultaneously
• Each character in both strings is visited at most twice (once in the main traversal and once in the counting loop)
• Therefore, for each word comparison, the time is O(n + wᵢ)
• Total time: O(m × n + Σᵢ₌₀^(m-1) wᵢ)

Space Complexity: O(1)

• The algorithm uses only a constant amount of extra space
• Variables i, j, k, c1, c2, m, and n are all primitive integers
• No additional data structures are created
• The space used does not depend on the input size

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Incorrect Group Size Validation

The Problem: A common mistake is misunderstanding when stretching is allowed. Many implementations incorrectly assume that if the source string has a group of size 3 or more, the target can have ANY smaller size. However, the target group size must still be at least 1.

Incorrect Implementation:

# Wrong: Doesn't ensure target has at least 1 character in the group
if source_group_count >= 3:
    # This would incorrectly allow target_group_count = 0
    return True

Correct Implementation:

# Must check that source >= target AND apply the size-3 rule
if source_group_count < target_group_count:
    return False
if source_group_count < 3 and source_group_count != target_group_count:
    return False

Pitfall 2: Not Fully Consuming Both Strings

The Problem: After the main loop, forgetting to verify that both strings were completely processed. This can lead to false positives where a shorter target word is incorrectly marked as stretchy.

Example Case:

• Source: "heeello"
• Target: "helo"
• Without the final check, after processing "he" from both strings, the function might return True even though "llo" remains unprocessed in source.

Incorrect Implementation:

while source_idx < source_len and target_idx < target_len:
    # ... processing logic ...
  
# Wrong: Missing final verification
return True

Correct Implementation:

while source_idx < source_len and target_idx < target_len:
    # ... processing logic ...
  
# Must ensure both strings are fully consumed
return source_idx == source_len and target_idx == target_len

Pitfall 3: Off-by-One Errors in Group Counting

The Problem: When counting consecutive characters, it's easy to make off-by-one errors, especially when updating the indices after counting.

Incorrect Implementation:

# Wrong: This creates an off-by-one error
source_group_count = 1  # Start with 1
source_idx += 1
while source_idx < source_len and source[source_idx] == source[source_idx - 1]:
    source_group_count += 1
    source_idx += 1
# source_idx is now already moved, causing issues

Correct Implementation:

# Use a separate variable for counting
source_group_end = source_idx
while source_group_end < source_len and source[source_group_end] == source[source_idx]:
    source_group_end += 1
source_group_count = source_group_end - source_idx
source_idx = source_group_end  # Clean update

Pitfall 4: Mishandling Edge Cases with Single Characters

The Problem: Failing to properly handle cases where a character appears only once in either string, particularly when applying the "group of 3" rule.

Example Case:

• Source: "abcd" (each character appears once)
• Target: "abc"
• Since each group in source has size 1 (less than 3), each corresponding group in target must also have exactly size 1.

Solution: The code correctly handles this with the condition:

if source_group_count < 3 and source_group_count != target_group_count:
    return False

This ensures single characters (or pairs) must match exactly and cannot be stretched.