Sponsored
Sponsored
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.
1function countCharacters(words, chars) {
2 let charCount = new Array(26).fill(0);
3 for (let c of chars) {
4 charCount[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
5 }
6 let result = 0;
7 for (let word of words) {
8 let wordCount = new Array(26).fill(0);
9 for (let c of word) {
10 wordCount[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
11 }
12 let canForm = true;
13 for (let i = 0; i < 26; i++) {
14 if (wordCount[i] > charCount[i]) {
15 canForm = false;
16 break;
17 }
18 }
19 if (canForm) {
20 result += word.length;
21 }
22 }
23 return result;
24}
25
26const words = ["cat", "bt", "hat", "tree"];
27const chars = "atach";
28console.log(countCharacters(words, chars)); // Output: 6This JavaScript solution uses array data structures to calculate the frequency of characters in 'chars'. For each word, it compares its required character count to the available character count and sums up the lengths accordingly.
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.
1def count_characters(words, chars):
2
Using Python's Counter for character mapping, this solution compares each word's character needs to that available in 'chars'. It uses a single line check with all() to determine if the word can be formed.