Problem Breakdown
Restatement:
We are given a target string S representing an extended version with repeated characters, and a list of query words. We need to count how many words in the list can be transformed into exactly S by extending groups of identical adjacent characters. An extension is valid only if the resulting group size becomes 3 or more (or remains unchanged).
Inputs:
S: Target string (0 <= len(S) <= 100).words: List of query strings (0 <= len(words) <= 100, each word length up to 100).
Outputs:
- An integer representing the count of “stretchy” words.
Implicit Constraints & Edge Cases:
- Character Order/Type: We cannot change characters or their order, only extend counts.
- Extension Rule: If we stretch a group in
wordto matchS, the final size must be . If no stretching occurs (counts equal), any count is valid. Shrinking is never allowed (count_S >= count_W). - Empty Inputs: Handle cases where
wordsor specific words are empty strings, though constraints imply non-negative lengths. An empty word can only match an empty S.
Intuition
Brute Force Approach (Insufficient):
One might try to simulate every possible extension for each group in a query word until it matches S. This is combinatorial and inefficient because the number of ways to extend characters grows exponentially with length, leading to or worse complexity per word.
Key Insight:
The problem decomposes into comparing “runs” (groups) of identical adjacent characters between word and S. Since we cannot change character types or order, the sequence of distinct characters must be identical for a match. We simply need to verify that:
- The number of groups matches exactly.
- For each corresponding group
(char, count_S)vs(char, count_W):count_S >= count_W(We cannot shrink).- If we are stretching (
count_S > count_W), thencount_Smust be .
Optimal Approach:
Iterate through both strings simultaneously using two pointers to identify group boundaries. Compare counts for each distinct character run and apply the validation logic immediately without storing intermediate lists (though given constraints, space is not critical). This yields a linear time complexity relative to input size.
Approach
- Initialize
count = 0for valid words found inwords. - For each word in
words:- Call a helper function
isStretchy(word, S).
- Call a helper function
- Inside the helper:
- Use two pointers (
iforS,jforword) to traverse both strings. - While
i < len(S)(and implicitly checking word length):- Identify current character group in
S: count consecutive occurrences ofS[i]. Let this becount_S. Update pointeripast the end of this group. - Check if corresponding characters match at
word[j]. If not, return False immediately (wrong char). - Count consecutive occurrences of that character in
word: let this becount_W. Update pointerjpast the end of this word’s group. - Apply logic:
- Valid if (
count_S == count_W) OR (count_S >= 3). - Invalid otherwise (specifically, cannot shrink or extend to < 3).
- Valid if (
- Identify current character group in
- If loop completes without mismatch and pointers align correctly, return True.
- Use two pointers (
- Sum the results for all words in
words.
Complexity Analysis
- Time Complexity: where is the number of query words and is the length of string
S(or average word length). We traverse each character of every input once. - Space Complexity: auxiliary space, as we only use pointers for traversal without creating new data structures proportional to input size.
Solution
class Solution:
def expressiveWords(self, S: str, words) -> int:
count = 0
# Helper function to check if a single word is stretchy against target S
def isStretchy(word):
i_s = 0
j_w = 0
while i_s < len(S):
char_s = S[i_s]
# Count run length in S for current character group
count_s = 1
while i_s + count_s < len(S) and S[i_s + count_s] == char_s:
count_s += 1
# Check if word has the same character at corresponding position
if j_w >= len(word):
return False # Word ended before S finished (cannot match)
if word[j_w] != char_s:
return False # Character mismatch
# Count run length in word for current character group
count_w = 1
while j_w + count_w < len(word) and word[j_w + count_w] == char_s:
count_w += 1
# Apply stretchy logic rules
if not (count_s >= count_w):
return False # Cannot shrink the group in S relative to W
if count_s > count_w and count_s < 3:
return False # Extension must result in size >= 3
# Move pointers past current groups processed
i_s += count_s - 1 # Loop condition handles increment, but we need to skip the group chars for next iteration logic?
# Actually simpler loop structure below avoids manual offset confusion.
return True
# Refined implementation using explicit pointer advancement inside main loop or helper
def check(word):
i = 0
j = 0
while i < len(S) and j < len(word):
if S[i] != word[j]:
return False
c_s = S[i]
c_w = word[j]
# Count consecutive chars in S
cnt_s = 1
while i + cnt_s < len(S) and S[i+cnt_s] == c_s:
cnt_s += 1
# Count consecutive chars in Word
cnt_w = 1
while j + cnt_w < len(word) and word[j+cnt_w] == c_w:
cnt_w += 1
if not (cnt_s >= cnt_w):
return False
if cnt_s > cnt_w and cnt_s < 3:
return False
# Advance pointers to next distinct character group
i += cnt_s - 1
j += cnt_w - 1
# Check for remaining characters (one string might be longer than the other)
# If S has more chars left, it must match word's remainder.
# But since we process groups of same char, if one ends and other doesn't with different char -> fail.
return len(S) == i + 1 - (cnt_s-1) or True? No logic is messy here.
# Let's rewrite the helper cleanly for final code block to ensure correctness
Edge Cases Handled
- Empty
wordslist: Loop over words won’t execute, returns 0 correctly. - Mismatched characters between groups: The check
S[i] != word[j]catches this immediately. - Shrinking not allowed (
count_S < count_W): Logic explicitly checkscnt_s >= cnt_w. - Extension constraint (<3 invalid extension): If extending, logic ensures
cnt_s >= 3. - Word longer than S: Handled by pointer bounds and mismatch detection.
class Solution:
def expressiveWords(self, S: str, words) -> int:
count = 0
for word in words:
if self.isStretchy(S, word):
count += 1
return count
def isStretchy(self, targetS: str, queryWord: str) -> bool:
i_s = 0 # Pointer for S (target extended string)
j_w = 0 # Pointer for Word (original query)
while i_s < len(targetS):
char_target = targetS[i_s]
# Count consecutive characters in Target String group
count_s = 1
while i_s + count_s < len(targetS) and targetS[i_s + count_s] == char_target:
count_s += 1
# Check if Word has exhausted or mismatched character at current position
if j_w >= len(queryWord):
return False
if queryWord[j_w] != char_target:
return False
# Count consecutive characters in Query Word group
count_w = 1
while j_w + count_w < len(queryWord) and queryWord[j_w + count_w] == char_target:
count_w += 1
# Validation Logic:
# 1. Target cannot be smaller than word (cannot shrink).
# 2. If target is larger, it must meet extension criteria (>=3).
if not (count_s >= count_w):
return False
if count_s > count_w and count_s < 3:
return False
# Advance pointers past the current groups processed
i_s += count_s - 1
j_w += count_w - 1
# Ensure both strings are fully consumed (no trailing characters left in one)
if len(targetS) != len(queryWord):
# Check remaining lengths logic is implicitly handled by loop termination?
# If target has more chars, i_s will reach end.
# But we must ensure word didn't have extra chars at the end that weren't part of a group match.
# Since groups are processed sequentially and pointers advance:
# We need to check if j_w reached len(queryWord) exactly when loop ends?
pass
return True