1. Find Words That Can Be Formed by Characters (LeetCode)
Model answer
The task
Given a list of words and a collection of available characters, return the total length of the words that can be formed using those characters. Each character can be used only as many times as it appears in the collection.
Key idea
Count the available characters once. A word is formable exactly when its count for every character does not exceed the available count.
Approach
- Build a frequency counter for the available characters.
- For each word, count its characters.
- Check whether every needed count is available.
- Add the word’s length to the total when it passes the check.
- Return the total.
from collections import Counter
from typing import List
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
available = Counter(chars)
total_length = 0
for word in words:
needed = Counter(word)
if all(needed[ch] <= available[ch] for ch in needed):
total_length += len(word)
return total_length
Complexity:
- Time: O(C + S), where C is the length of
charsand S is the total length of all words. - Space: O(U + M), where U is the number of distinct characters in
charsand M is the maximum word length, for the counters.
Common follow-ups
- What if many word lists use the same characters? Reuse the available-character counter across all lists.
- How could you avoid counting each word’s characters from scratch? Precompute word counters if the same words are checked repeatedly.
- What if the character collection is updated between queries? Update its frequency counts and evaluate words against the current counts.