#1160

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find Words That Can Be Formed by Characters

Compute the total length of words that can be fully constructed from given characters using array scanning and hash mapping techniques.

array hash table string counting

Problem Statement

Given an array of strings words and a string chars, determine which words can be fully formed by using characters from chars. Each character in chars can be used at most once per word, and all letters must be accounted for to consider a word valid.

Return the sum of lengths of all words that can be formed. For example, given words = ["cat","bt","hat","tree"] and chars = "atach", the words "cat" and "hat" are valid, yielding a total length of 6.

Examples

Example 1

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

Output: 6

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

Example 2

Input: words = ["hello","world","leetcode"], chars = "welldonehoneyr"

Output: 10

The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.

Constraints

1 <= words.length <= 1000
1 <= words[i].length, chars.length <= 100
words[i] and chars consist of lowercase English letters.

Solution Approach

Build a character frequency map for chars

Count each character in chars using a hash table or array of size 26 to track how many times each letter can be used. This sets up an O(1) lookup for checking individual words.

Verify each word independently

Iterate over every word in words and build a temporary frequency count. Compare against the chars map to ensure no character is used more than available. Only count words that pass this check, which aligns with the array scanning plus hash lookup pattern.

Accumulate the total length

For each valid word, add its length to a running sum. Return the final sum after processing all words. This step emphasizes efficiency by scanning arrays and using hash lookups without modifying the original chars data.

Complexity Analysis

Metric	Value
Time	O(n + m \cdot k)
Space	O(1)

Time complexity is O(n + m * k) where n is the length of chars, m is the number of words, and k is the average word length. Space complexity is O(1) since the frequency map uses a fixed-size array of 26 for lowercase letters.

What Interviewers Usually Probe

Pay attention to independent word checks to avoid overcounting characters.
Use a fixed-size hash table for character counting to optimize for repeated lookups.
Emphasize correctness over clever shortcuts; each word must validate against the chars map precisely.

Common Pitfalls or Variants

Common pitfalls

Reusing chars counts across multiple words without resetting for each word.
Neglecting words with repeated characters exceeding chars availability.
Confusing word length sum with word count; only lengths of valid words matter.

Follow-up variants

Return the list of words that can be formed instead of the sum of lengths.
Allow unlimited reuse of characters from chars and sum lengths accordingly.
Modify chars dynamically to remove used characters permanently across words.

FAQ

What is the main pattern used in 'Find Words That Can Be Formed by Characters'?

The main pattern is array scanning combined with a hash lookup for character frequency to verify each word independently.

Can I reuse the chars for multiple words?

No, each word must be validated independently against the original chars counts; characters cannot carry over.

What data structure efficiently tracks character counts?

A fixed-size array of length 26 or a hash table mapping characters to counts works best for fast O(1) lookups.

How do I handle words with repeated letters?

Check that the frequency of each letter in the word does not exceed the frequency in chars; otherwise, the word is invalid.

Is the sum of lengths or number of words returned?

You return the sum of lengths of all valid words, not the count of words.

terminal

Solution

Solution 1: Counting

We can use an array $cnt$ of length $26$ to count the occurrence of each letter in the string $chars$.

1

2

3

4

5

6

7

8

9

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

Continue Practicing

#1366 rank teams by votes #819 most common word #811 subdomain visit count