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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Expressive Words

Number: 827

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a string s and an array of query strings words, count the number of words that are "stretchy." A word is considered stretchy if it can be transformed into s by repeatedly extending groups of characters. In an extension operation, you can take a group of adjacent identical characters in the word and add more of the same character such that the group’s length becomes at least 3. The goal is to determine exactly how many words from the list can be transformed into s following the given extension rules.

Key Insights

  • Both the target string s and each candidate word can be broken down into groups of repeated characters.
  • Use a two-pointer technique to iterate over s and the query word simultaneously by comparing corresponding character groups.
  • For each group, the characters must match. Let countS be the group length in s and countW be the group length in the word.
  • It is valid if countS equals countW, or if countS is at least 3 and countS is greater than countW (allowing the extension).
  • If any group does not satisfy the conditions, the word cannot be stretched to match s.

Space and Time Complexity

Time Complexity: O(N * L) where N is the number of words and L is the average length of a word (since each word is scanned in linear time relative to its length). Space Complexity: O(1) additional space, not counting the space used for the input.

Solution

The solution uses a two-pointer approach to simultaneously traverse the string s and the query word. For each corresponding group of consecutive characters, we count the lengths. We then verify the following:

  1. The characters in the current groups match.
  2. The group length in s must either be equal to the group length in the query word, or be greater or equal to 3 and at least one more than the query word group length to allow for the extension. If any group comparison fails, the word is not stretchy. We repeat this process for every word in the list and count those that satisfy the criteria.

Data structures used include simple variables for pointers and counters. The algorithmic approach leverages two-pointer iteration and in-place group counting without any extra storage, making it straightforward and efficient.

Code Solutions

# Function to check if a word is stretchy compared to the string s.
def is_stretchy(s: str, word: str) -> bool:
    i, j = 0, 0
    while i < len(s) and j < len(word):
        # if current characters do not match, word cannot be stretched to s.
        if s[i] != word[j]:
            return False

        # Count the number of same characters in s
        count_s = 1
        while i + 1 < len(s) and s[i] == s[i + 1]:
            count_s += 1
            i += 1

        # Count the number of same characters in word
        count_w = 1
        while j + 1 < len(word) and word[j] == word[j + 1]:
            count_w += 1
            j += 1

        # Check if the current group is valid:
        # They are equal, or s's group is larger and at least 3 characters long.
        if count_s != count_w and (count_s < 3 or count_s < count_w):
            return False

        # Move to the next group
        i += 1
        j += 1

    # Both pointers should finish exactly at the end of their strings.
    return i == len(s) and j == len(word)

def expressiveWords(s: str, words: [str]) -> int:
    stretchy_count = 0
    for word in words:
        if is_stretchy(s, word):
            stretchy_count += 1
    return stretchy_count

# Example usage:
if __name__ == "__main__":
    s = "heeellooo"
    words = ["hello", "hi", "helo"]
    print(expressiveWords(s, words))  # Expected output: 1
← Back to All Questions