Find Words That Can Be Formed by Characters: Character Frequency Pattern

You are given an array of strings words and a string chars. A word is "good" if it can be formed by characters from chars, where each character can only be used once. Return the sum of lengths of all good words.

This is LeetCode 1160: Find Words That Can Be Formed by Characters, and it is a clean introduction to the character frequency counting pattern. The same technique shows up in anagram detection, ransom note validation, and sliding window problems.

Why this problem matters

Character frequency counting is one of the most reusable building blocks in string problems. Once you can count characters and compare two frequency maps, you unlock a whole family of problems: checking anagrams, finding permutations in strings, building ransom notes from magazines, and grouping words by their character signatures. This problem gives you the simplest version of that skill. You build one frequency map, then check each word against it.

The key insight

Instead of trying to "cross off" characters one by one for each word, you build a frequency map of chars once. Then for each word, you build its own frequency map and compare. A word is formable if and only if, for every character in the word, the word's count for that character is less than or equal to the count in chars.

This turns a matching problem into a simple comparison of two dictionaries.

The algorithm:

1. Count the frequency of every character in chars.
2. For each word, count the frequency of every character in that word.
3. Compare the two frequency maps. If every character in the word has a count that is at most the count in chars, the word is "good."
4. Sum the lengths of all good words.

The solution

from collections import Counter

def count_characters(words: list[str], chars: str) -> int:
    chars_count = Counter(chars)
    total = 0

    for word in words:
        word_count = Counter(word)
        if all(word_count[ch] <= chars_count[ch] for ch in word_count):
            total += len(word)

    return total

Let's walk through what each piece does.

First, Counter(chars) builds a frequency map of the available characters. For chars = "atach", this gives {'a': 2, 't': 1, 'c': 1, 'h': 1}. This map is built once and reused for every word.

Then we loop through each word. For each one, we build Counter(word) to get its character frequencies. The all(...) check compares every character in the word against the available pool. If any character in the word requires more copies than chars provides, the word fails.

When a word passes, we add its length to total. Notice that we add len(word), not the word itself. The problem asks for the sum of lengths, not the words themselves.

Visual walkthrough

Let's trace through the example with chars = "atach" and words = ["cat", "bt", "hat", "tree"]. For each word, we compare its character frequencies against the available pool.

Notice how each word is checked independently against the original chars frequency map. We do not remove characters from the pool when a word succeeds. Each word gets a fresh comparison against the full set of available characters.

Complexity analysis

Time is O(n + sum of word lengths), where n is the length of chars. We do one pass through chars to build the frequency map, then one pass through each word to build and compare its frequency map. Each character in the input is examined exactly once.

Space is O(1) because the frequency maps are bounded by the size of the alphabet. With lowercase English letters, the maps never exceed 26 entries regardless of input size.

The building blocks

1. Frequency map construction

from collections import Counter
freq = Counter(s)

Building a frequency map from a string is the foundation of this problem. You will reuse this exact pattern in Valid Anagram (comparing two strings), Group Anagrams (using sorted frequency as a key), and Ransom Note (checking if one string's characters are a subset of another's).

2. Frequency map subset check

all(word_count[ch] <= chars_count[ch] for ch in word_count)

Checking whether one frequency map is "contained within" another is the core logic here. This same subset check appears in Ransom Note, Minimum Window Substring (with a sliding window twist), and any problem that asks "can I build X from Y's characters?"

Edge cases

• Empty words array: no words to check, return 0.
• Empty chars string: no characters available, so no word can be formed. Return 0.
• Word with repeated characters: "aab" needs a:2 and b:1. If chars only has one a, the word fails. The frequency comparison handles this naturally.
• Word longer than chars: a word with more characters than chars cannot be formed, since it would need more total characters than are available. The frequency check catches this without an explicit length comparison.
• Single character words: ["a", "b", "c"] with chars = "abc". Each single-character word is checked independently and all pass.
• All words valid: every word can be formed. Sum all their lengths.
• No words valid: no word can be formed. Return 0.

From understanding to recall

You now understand how frequency counting solves this problem: build a map of available characters, then check each word's map against it. The logic is simple and the code is short. But the value of this problem is not in solving it once. It is in making the frequency counting pattern automatic.

The next time you see a problem that asks "can this be built from those characters?" you want the Counter construction and subset check to come out of your fingers without thinking. That is the gap between understanding a pattern and owning it.

Spaced repetition closes that gap. You practice building the frequency map, writing the subset comparison, and assembling the loop from scratch at increasing intervals. After a few rounds, you see "character availability" in a problem description and the solution writes itself. No hesitation, no off-by-one errors, no forgetting whether to use <= or < in the comparison.

Related posts

• Contains Duplicate - The simplest hash set problem, teaching the "have I seen this before?" pattern that frequency counting builds on
• Valid Anagram - Compares two frequency maps for equality, the slightly harder cousin of subset checking
• Group Anagrams - Uses sorted character frequency as a hash map key, extending the counting pattern to grouping

CodeBricks breaks Find Words That Can Be Formed by Characters into its frequency map construction and subset checking building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a character counting problem shows up in your interview, you do not think about it. You just write it.