Introduction

In this blog post, we will explore how to solve the LeetCode problem "809" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

Sometimes people repeat letters to represent extra feeling. For example: "hello" -> "heeellooo" "hi" -> "hiiii" In these strings like "heeellooo", we have groups of adjacent letters that are all the same: "h", "eee", "ll", "ooo". You are given a string s and an array of query strings words. A query word is stretchy if it can be made to be equal to s by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is three or more. For example, starting with "hello", we could do an extension on the group "o" to get "hellooo", but we cannot get "helloo" since the group "oo" has a size less than three. Also, we could do another extension like "ll" -> "lllll" to get "helllllooo". If s = "helllllooo", then the query word "hello" would be stretchy because of these two extension operations: query = "hello" -> "hellooo" -> "helllllooo" = s. Return the number of query strings that are stretchy. Example 1: Input: s = "heeellooo", words = ["hello", "hi", "helo"] Output: 1 Explanation: We can extend "e" and "o" in the word "hello" to get "heeellooo". We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more. Example 2: Input: s = "zzzzzyyyyy", words = ["zzyy","zy","zyy"] Output: 3 Constraints: 1 <= s.length, words.length <= 100 1 <= words[i].length <= 100 s and words[i] consist of lowercase letters.

Explanation

Here's the solution to the stretchy words problem:

• Group and Compress: Represent both the target string s and each query word in a compressed format, storing the character and its count of consecutive occurrences.
• Stretchy Check: Compare the compressed representations. A query word is stretchy if each character appears in the same order as in s, and the count of that character in the query is either equal to the count in s or, the count in s is greater than or equal to 3, and the character in query is less than or equal to s.

• Count Stretchy Words: Iterate through the words, checking the stretchy condition for each word and incrementing the count of stretchy words.

• Runtime Complexity: O(N * M), where N is the number of words and M is the maximum length of a word.

• Storage Complexity: O(M), where M is the maximum length of a word (due to compressed representations).

Code

    def expressiveWords(s, words):
    """
    Determines the number of words that are stretchy with respect to the given string s.

    Args:
        s: The target string.
        words: A list of query strings.

    Returns:
        The number of stretchy words.
    """

    def compress(word):
        """Compresses a string into a list of (character, count) pairs."""
        compressed = []
        i = 0
        while i < len(word):
            j = i
            while j < len(word) and word[i] == word[j]:
                j += 1
            compressed.append((word[i], j - i))
            i = j
        return compressed

    s_compressed = compress(s)
    count = 0

    for word in words:
        word_compressed = compress(word)
        if len(s_compressed) != len(word_compressed):
            continue

        stretchy = True
        for i in range(len(s_compressed)):
            if s_compressed[i][0] != word_compressed[i][0]:
                stretchy = False
                break
            s_count = s_compressed[i][1]
            word_count = word_compressed[i][1]

            if s_count < word_count:
                stretchy = False
                break

            if s_count != word_count and s_count < 3:
                stretchy = False
                break

        if stretchy:
            count += 1

    return count