Watch 10 video solutions for Find Words That Can Be Formed by Characters, a easy level problem involving Array, Hash Table, String. This walkthrough by codestorywithMIK has 12,369 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of strings words and a string chars.
A string is good if it can be formed by characters from chars (each character can only be used once).
Return the sum of lengths of all good strings in words.
Example 1:
Input: words = ["cat","bt","hat","tree"], chars = "atach" Output: 6 Explanation: 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 Explanation: The strings that can be formed are "hello" and "world" so the answer is 5 + 5 = 10.
Constraints:
1 <= words.length <= 10001 <= words[i].length, chars.length <= 100words[i] and chars consist of lowercase English letters.Problem Overview: You receive a list of words and a string chars. Each character in chars can be used only once. The task is to determine which words can be constructed using those characters and return the total length of all valid words.
Approach 1: Character Frequency Counting (O(W * K) time, O(1) space)
The most efficient method relies on fixed-size frequency counting. First compute a frequency array of size 26 for chars. Then iterate through each word and build another 26-length counter for that word. Compare the counts: if any character appears more times in the word than in chars, the word cannot be formed. If all counts fit within the available supply, add the word’s length to the result. Since the alphabet is limited to lowercase English letters, the counter size remains constant, giving O(1) auxiliary space. This approach is straightforward and performs well because comparisons are constant-time operations over a small array.
This technique commonly appears in problems involving counting and string manipulation. You iterate through characters once, update counters, and validate availability using direct index access.
Approach 2: Map-based Character Counting (O(W * K) time, O(K) space)
This variation uses a hash map to track frequencies instead of a fixed array. Build a frequency map for chars. For each word, construct another map while iterating through its characters. During the check phase, verify that each character’s frequency in the word does not exceed the frequency in the base map. If all checks pass, accumulate the word length.
The logic mirrors the array-counting approach but uses dynamic storage rather than fixed indexing. Time complexity remains O(W * K), where W is the number of words and K is the average word length. Space complexity becomes O(K) due to per-word maps. This approach is useful when working with larger character sets or when the problem is framed around hash table operations.
Recommended for interviews: Character Frequency Counting. Interviewers expect you to recognize that the alphabet size is fixed and replace hash maps with a small array. The map-based approach still demonstrates correct reasoning, but the array solution shows stronger awareness of constant-space optimizations and typical patterns used in array-based counting problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Character Frequency Counting (Array) | O(W * K) | O(1) | Best choice when characters are limited (e.g., lowercase English letters). Fast lookups and minimal memory. |
| Map-based Character Counting | O(W * K) | O(K) | Useful when the character set is large or unknown and fixed-size arrays are not practical. |