Sponsored
Sponsored
In this approach, we will use a hash map (or dictionary) to store the frequency of each character for each word. We then update a common frequency count table that holds the minimum frequency of each character across all words. This ensures that only characters existing in all words are recorded.
Time Complexity: O(N*K) where N is the number of words and K is the average length of the words. Space Complexity: O(1) since the space does not scale with input size.
1function findCommonChars(words) {
2 let minCount = new Array(26).fill(Infinity);
3
4 for (let word of words) {
5 let count = new Array(26).fill(0);
6 for (let char of word) {
7 count[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
8 }
9 for (let i = 0; i < 26; i++) {
10 minCount[i] = Math.min(minCount[i], count[i]);
11 }
12 }
13
14 let result = [];
15 for (let i = 0; i < 26; i++) {
16 for (let j = 0; j < minCount[i]; j++) {
17 result.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
18 }
19 }
20 return result;
21}
22
23let words = ['bella', 'label', 'roller'];
24console.log(findCommonChars(words));In this JavaScript solution, we use arrays to store and manipulate counts, taking minimum values to determine common characters.
We can alternatively use direct character arrays to represent frequencies and update these arrays with each subsequent word processed. Starting with the first word's character frequencies, we iteratively compute the minimum with the rest.
Time Complexity: O(N*K). Space Complexity: O(1) for constant sized arrays.
1#include <vector>
#include <string>
#include <climits>
std::vector<char> findCommonChars(const std::vector<std::string>& words) {
std::vector<int> minFrequency(26, INT_MAX);
for (const auto& word : words) {
std::vector<int> freq(26, 0);
for (const char& c : word) {
freq[c - 'a']++;
}
for (int i = 0; i < 26; ++i) {
minFrequency[i] = std::min(minFrequency[i], freq[i]);
}
}
std::vector<char> result;
for (int i = 0; i < 26; ++i) {
for (int j = 0; j < minFrequency[i]; ++j) {
result.push_back('a' + i);
}
}
return result;
}
int main() {
std::vector<std::string> words = {"bella", "label", "roller"};
std::vector<char> results = findCommonChars(words);
for (char c : results) {
std::cout << c << " ";
}
std::cout << std::endl;
return 0;
}Here, we maintain a running frequency count, keeping track of the minimum frequency across all given words. It processes character counts efficiently by leveraging the fixed size of the alphabet.