1160. Find Words That Can Be Formed by Characters - Explanation

1. Hash Map (Two Pass)

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        count = Counter(chars)
        res = 0

        for w in words:
            cur_word = Counter(w)
            good = True
            for c in cur_word:
                if cur_word[c] > count[c]:
                    good = False
                    break
            if good:
                res += len(w)
        return res

Time & Space Complexity

Time complexity: $O(n + (m * k))$
Space complexity: $O(1)$ since we have at most $26$ different characters.

Where $n$ is the length of $chars$ , $m$ is the number of words and $k$ is the average length of each word.

2. Hash Map (One Pass)

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        count = Counter(chars)
        res = 0

        for w in words:
            cur_word = defaultdict(int)
            good = True
            for c in w:
                cur_word[c] += 1
                if cur_word[c] > count[c]:
                    good = False
                    break
            if good:
                res += len(w)
        return res

Time & Space Complexity

Time complexity: $O(n + (m * k))$
Space complexity: $O(1)$ since we have at most $26$ different characters.

Where $n$ is the length of $chars$ , $m$ is the number of words and $k$ is the average length of each word.

3. Hash Table

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        count = [0] * 26
        for c in chars:
            count[ord(c) - ord('a')] += 1

        org = count[:]
        res = 0

        for w in words:
            good = True
            for c in w:
                i = ord(c) - ord('a')
                count[i] -= 1
                if count[i] < 0:
                    good = False
                    break
            if good:
                res += len(w)

            for i in range(26):
                count[i] = org[i]
        return res

Time & Space Complexity

Time complexity: $O(n + (m * k))$
Space complexity: $O(1)$ since we have at most $26$ different characters.

Where $n$ is the length of $chars$ , $m$ is the number of words and $k$ is the average length of each word.