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.In #1160 Find Words That Can Be Formed by Characters, the goal is to determine which words in a list can be constructed using the characters from a given string. Each character in the source string can only be used as many times as it appears. The key idea is to track character frequencies.
A common and efficient approach is to use a frequency counter (such as an array of size 26 or a hash table) to store the count of each character in chars. For every word in the list, create a temporary copy of this frequency structure and decrement counts as characters are used. If any character’s count becomes negative, that word cannot be formed.
If the word is valid, add its length to the total result. This counting technique avoids expensive repeated searches and keeps the solution efficient. The overall approach mainly involves iterating through the words and performing character counting checks, resulting in linear behavior relative to the total input size.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Character Frequency Counting (Array / Hash Map) | O(W * K + C) | O(1) |
Nick White
Use these hints if you're stuck. Try solving on your own first.
Solve the problem for each string in <code>words</code> independently.
Now try to think in frequency of letters.
Count how many times each character occurs in string <code>chars</code>.
To form a string using characters from <code>chars</code>, the frequency of each character in <code>chars</code> must be greater than or equal the frequency of that character in the string to be formed.
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.
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.
1#include <stdio.h>
2#include <string.h>
3
4int countCharacters(char **words, int wordsSize, char *chars) {
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.
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.
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.
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_map>
5using namespace std;
int countCharacters(vector<string>& words, string chars) {
unordered_map<char, int> charMap;
for (char c : chars) {
charMap[c]++;
}
int result = 0;
for (string word : words) {
unordered_map<char, int> wordMap;
for (char c : word) {
wordMap[c]++;
}
bool canForm = true;
for (auto& entry : wordMap) {
if (entry.second > charMap[entry.first]) {
canForm = false;
break;
}
}
if (canForm) {
result += word.length();
}
}
return result;
}
int main() {
vector<string> words = {"cat", "bt", "hat", "tree"};
string chars = "atach";
cout << countCharacters(words, chars) << endl; // Output: 6
return 0;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Counting helps efficiently track how many times each character can be used. By decrementing counts while checking a word, we can quickly detect if the word requires more characters than available.
While the exact problem may not always appear, similar frequency counting and string validation problems are common in FAANG-style interviews. Practicing this problem helps build a strong foundation in hash tables and counting techniques.
A fixed-size frequency array of length 26 is usually the best choice because the input consists of lowercase English letters. A hash map can also work, but the array is faster and uses constant space.
The optimal approach uses a character frequency counter for the given chars string. For each word, compare its character usage with the available counts and ensure no character is used more times than allowed.
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.