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.
1#include <stdio.h>
2#include <string.h>
3
4int countCharacters(char **words, int wordsSize, char *chars) {
5 int charCount[26] = {0};
6 for (int i = 0; chars[i] != '\0'; i++) {
7 charCount[chars[i] - 'a']++;
8 }
9 int result = 0;
10 for (int i = 0; i < wordsSize; i++) {
11 int wordCount[26] = {0};
12 for (int j = 0; words[i][j] != '\0'; j++) {
13 wordCount[words[i][j] - 'a']++;
14 }
15 int canForm = 1;
16 for (int k = 0; k < 26; k++) {
17 if (wordCount[k] > charCount[k]) {
18 canForm = 0;
19 break;
20 }
21 }
22 if (canForm) {
23 result += strlen(words[i]);
24 }
25 }
26 return result;
27}
28
29int main() {
30 char *words[] = {"cat", "bt", "hat", "tree"};
31 char chars[] = "atach";
32 int wordsSize = 4;
33 printf("%d\n", countCharacters(words, wordsSize, chars)); // Output: 6
34 return 0;
35}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;
}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.