💬 Discord
Sign In
NeetCode #68LC-1160EasyArrays & Hashing
← Back to All Problems

#68 · #1160 · Find Words That Can Be Formed by Characters(拼写单词)

📌 Problem Statement & Constraints

You are given an array of strings words and a string chars. A string is good if it can be formed using only the letters of chars, each letter used at most as many times as it appears in chars. Return the sum of the lengths of all good strings. Constraints: 1 <= words.length <= 1000, 1 <= chars.length <= 100, all lowercase letters.

💡 Core Algorithmic Approaches

  1. Count the available letters in chars once.
  2. For each word, count its letters and verify that no letter is required more times than available.
  3. If the word passes, add its length to the total.
  4. The whole-word check is what distinguishes this from a mere character-set test -- multiplicity matters.

💻 Benchmark Python3 Implementation

class Solution:
    def countCharacters(self, words: List[str], chars: str) -> int:
        from collections import Counter
        avail = Counter(chars)
        total = 0
        for w in words:
            need = Counter(w)
            if all(need[ch] <= avail[ch] for ch in need):
                total += len(w)
        return total

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(|chars| + sum of word lengths): each word is counted once and compared against the available letters.
💾 Space Complexity
O(k) for the two counters, with k <= 26.

⚠️ Interview Pitfalls & Follow-ups

  • Checking only set(w) <= set(chars): this ignores multiplicity, so chars = "a" would wrongly accept the word "aa".
  • Iterating avail instead of need: you must check every letter the word needs, not every letter available.
  • Mutating the available counts across words: each word must be tested against the full original chars.