Find Words That Can Be Formed by Characters - Solution & Explanation
Problem Statement
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]andcharsconsist of lowercase English letters.
Approach Overview
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 1: Character Frequency Counting
This approach involves counting the frequency of each character in the 'chars' string. For each word, check if the word can be constructed using these characters, respecting their frequencies.
This solution counts the frequency of each character in the 'chars' array using an integer array of size 26. For each word, it creates a frequency array to check if the word can be formed without exceeding the available characters and their counts.
Complexity
Time Complexity: O(N*K + C), where N = number of words, K = average length of the word, C = length of 'chars'.
Space Complexity: O(1), as the auxiliary space used is constant, i.e., the two arrays of size 26.
Approach 2: Map-based Character Counting
This approach utilizes hash maps to count the frequency of characters in both the 'chars' string and each word. The map allows for dynamic sizing and flexibility with character counts.
This solution counts the frequencies of characters using hash maps for both 'chars' and each word. It checks if the words can be formed by comparing counts in these maps and adds the lengths of words that can be formed.
Complexity
Time Complexity: O(N*K + C), where N = number of words, K = average length of the word, C = length of 'chars'.
Space Complexity: O(1), additional space overhead is minimal with the unordered maps.
Approach 3: Counting
We can use an array cnt of length 26 to count the occurrence of each letter in the string chars.
Then we traverse the string array words. For each string w, we use an array wc of length 26 to count the occurrence of each letter in the string w. If for each letter c, wc[c] leq cnt[c], then we can spell the string w with the letters in chars, otherwise we cannot spell the string w. If we can spell the string w, then we add the length of the string w to the answer.
After the traversal, we can get the answer.
The time complexity is O(L), and the space complexity is O(C). Here, L is the sum of the lengths of all strings in the problem, and C is the size of the character set. In this problem, C = 26.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Character Frequency Counting | Time Complexity: O(N*K + C), where N = number of words, K = average length of the word, C = length of 'chars'. |
| Map-based Character Counting | Time Complexity: O(N*K + C), where N = number of words, K = average length of the word, C = length of 'chars'. |
| Counting | — |
Detailed Complexity Analysis
| 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. |
Video Solution
Find Words That Can Be Formed by Characters | META | Leetcode 1160 • codestorywithMIK • 13,876 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find Words That Can Be Formed by Characters easy or hard?
Find Words That Can Be Formed by Characters Python/Java solution
How to solve Find Words That Can Be Formed by Characters in O(n)?
What is the best approach for Find Words That Can Be Formed by Characters?
Is Find Words That Can Be Formed by Characters asked at Google/Amazon/Meta?
What data structure is used in Find Words That Can Be Formed by Characters?
What is the time complexity of Find Words That Can Be Formed by Characters?
Ready to solve this problem?
Practice Find Words That Can Be Formed by Characters with our built-in code editor and test cases.
Practice on FleetCode