algoadvance

Before we dive into the solution, let’s clarify the problem statement a bit:

1. Input Clarification:
   • You have a string s.
   • You have an array of words words.
2. Output Requirement:
   • You need to return the number of words that are “stretchy” relative to the string s.
3. Definition of Stretchy:
   • A word is considered stretchy if it can be made to match s by expanding some of its characters into a group of repeated characters.
   • This expansion must occur where a character in s already forms a group of repeated characters of length 3 or more.
   • For example, “heeellooo” is stretchy relative to “hello” because ‘e’ can be stretched to “ee” and ‘o’ can be stretched to “ooo”.

Strategy

1. Character Grouping:
   • Group characters together and note their counts for both s and each word in words. This helps in comparing the structure.
2. Comparison:
   • Compare each word’s grouped characters with that of s.
   • Ensure that the words have the same character structure and follow the stipulation where characters in s can extend to at least 3 for “stretchiness” but not vice versa.

Steps

1. Write a function to group characters and their counts.
2. Compare the character groups of s with each word to determine “stretchiness”.
3. Count how many words are stretchy.

Code

def expressive_words(s: str, words: list) -> int:
    def get_char_groups(word):
        groups = []
        i, n = 0, len(word)
        while i < n:
            char = word[i]
            count = 0
            while i < n and word[i] == char:
                i += 1
                count += 1
            groups.append((char, count))
        return groups
    
    def is_stretchy(s_group, w_group):
        if len(s_group) != len(w_group):
            return False

        for (sc, sc_count), (wc, wc_count) in zip(s_group, w_group):
            if sc != wc:
                return False
            if sc_count < wc_count:
                return False
            if sc_count > wc_count and sc_count < 3:
                return False
        
        return True

    s_group = get_char_groups(s)
    count_stretchy_words = 0

    for word in words:
        w_group = get_char_groups(word)
        if is_stretchy(s_group, w_group):
            count_stretchy_words += 1

    return count_stretchy_words

# Example Usage
s = "heeellooo"
words = ["hello", "hi", "helo"]
print(expressive_words(s, words))  # Output: 1

Time Complexity

• The get_char_groups function runs in O(n) where n is the length of the word involved, since it involves a single scan of the word.
• is_stretchy runs in O(k) where k is the number of groups in the word.
• The overall time complexity for expressive_words is O(n * m) where n is the length of s and m is the average length of words in the list since each word in words is processed individually.

This solution should efficiently determine the number of stretchy words relative to the string s.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?