Find Words That Can Be Formed by Characters — LeetCode 1160 Python Solution

The problem

You are given an array of strings words and a string chars. A string is good if it can be formed by characters from chars (each character can only be used once for each word in words).

Example

Input

words = ["cat","bt","hat","tree"], chars = "atach"

Output

6

Explanation

The strings that can be formed are "cat" and "hat" so the answer is 3 + 3 = 6.

Python solution

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        cnt = Counter(chars)
        ans = 0
        for w in words:
            wc = Counter(w)
            if all(cnt[c] >= v for c, v in wc.items()):
                ans += len(w)
        return ans

Complexity

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 1160. Find Words That Can Be Formed by Characters is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table and Counting.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems