#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/google-interview-prep-v2/coding-patterns-i-arrays-strings-hash-maps/leetcode-809-expressive-words-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/google-interview-prep-v2/coding-patterns-i-arrays-strings-hash-maps/leetcode-809-expressive-words-implementation

Repovive

LeetCode 809 Expressive Words - Implementation - Coding Patterns I: Arrays, Strings & Hash Maps | Google Interview Prep | Repovive

Repovive.

Google Interview Prep6 sections · 128 units7h total

Open in Course

LeetCode 809 Expressive Words - Implementation

The code

Group consecutive characters, then compare groups pairwise. A group stretches only if the count in s is $3$ or more.

function getGroups(str):
    groups = []
    i = 0
    while i < str.length:
        ch = str[i]
        count = 0
        while i < str.length and str[i] == ch:
            count += 1
            i += 1
        groups.append((ch, count))
    return groups

function expressiveWords(s, words):
    sGroups = getGroups(s)
    result = 0
    for word in words:
        wGroups = getGroups(word)
        if len(wGroups) != len(sGroups):
            continue
        stretchy = true
        for i in range(len(sGroups)):
            sc, sn = sGroups[i]
            wc, wn = wGroups[i]
            if sc != wc:
                stretchy = false
                break
            if sn != wn and sn < 3:
                stretchy = false
                break
            if wn > sn:
                stretchy = false
                break
        if stretchy:
            result += 1
    return result

$O(n + k \cdot m)$ time, $O(n)$ space.