Find Words That Can Be Formed by Characters

How it works

Since we only have lowercase letters, we can use a fixed-size array of 26 elements instead of a hash map. This is more cache-friendly and avoids hash function overhead. We decrement counts as we use characters and reset the array for each new word using a stored original copy.

Steps

1. Create an array count of size 26 and populate it with frequencies from chars.
2. Store a copy of count as org for resetting.
3. For each word:
   • For each character, decrement count[c - 'a'].
   • If it goes negative, the word is invalid; break early.
   • If valid, add the word's length to res.
   • Reset count to org for the next word.
4. Return the total length.

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.

Things to watch for

Modifying the Original Character Count Map

When checking each word, you must use a fresh copy of the character counts or reset after each word. A common mistake is decrementing the original count map without restoring it, causing subsequent words to have fewer available characters than they should.

Checking Character Presence Without Frequency

It is not enough to check if a character exists in chars; you must verify that the frequency of each character in the word does not exceed its frequency in chars. For example, "aab" cannot be formed from "ab" even though both 'a' and 'b' are present.

from typing import List

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

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        vector<int> count(26, 0);
        for (char c : chars) {
            count[c - 'a']++;
        }

        vector<int> org = count;
        int res = 0;

        for (string& w : words) {
            bool good = true;
            for (char& c : w) {
                int i = c - 'a';
                count[i]--;
                if (count[i] < 0) {
                    good = false;
                    break;
                }
            }
            if (good) {
                res += w.length();
            }
            for (int i = 0; i < 26; i++) {
                count[i] = org[i];
            }
        }
        return res;
    }
};