We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Expressive Words

Difficulty: Medium

Problem Description

Given a string s and an array of query strings words, a query word is stretchy if it can be made equal to s by any number of applications of the extension operation. The extension operation allows you to choose a group of adjacent characters and add more characters to that group, as long as the group becomes three or more characters. Return the number of query strings that are stretchy.

Key Insights

  • Groups of adjacent letters in the string can be increased in size to three or more.
  • Each character in the string s must have a corresponding character in the query word with the same count or more.
  • If a character group in the query word has fewer than three characters, it cannot be stretched.
  • The problem can be effectively solved using a two-pointer approach to compare character groups.

Space and Time Complexity

Time Complexity: O(n * m), where n is the number of words in the query and m is the average length of the words. Space Complexity: O(1), as we are using a constant amount of space for pointers.

Solution

To solve this problem, we will:

  1. Use two pointers to traverse both the string s and each word in the words array.
  2. For each character in s and the corresponding character in the query word, we will count the lengths of the groups of characters.
  3. Check if the group lengths satisfy the conditions for being stretchy:
    • If the group in the query word is smaller than three, it should match exactly.
    • If the group in the query word is three or more, it can be stretched.
  4. Count all the stretchy words and return the total.

Code Solutions

def expressiveWords(s, words):
    def count_groups(word):
        groups = []
        count = 1
        for i in range(1, len(word)):
            if word[i] == word[i - 1]:
                count += 1
            else:
                groups.append(count)
                count = 1
        groups.append(count)
        return groups

    s_groups = count_groups(s)
    result = 0

    for word in words:
        word_groups = count_groups(word)
        if len(word_groups) != len(s_groups):
            continue
        
        stretchy = True
        for s_count, w_count in zip(s_groups, word_groups):
            if w_count > s_count or (s_count < 3 and s_count != w_count):
                stretchy = False
                break
        if stretchy:
            result += 1

    return result
← Back to All Questions