1170. Compare Strings by Frequency of the Smallest Character
Let's define a function f(s)
over a non-empty string s
, which calculates the frequency of the smallest character in s
. For example, if s = "dcce"
then f(s) = 2
because the smallest character is "c"
and its frequency is 2.
Now, given string arrays queries
and words
, return an integer array answer
, where each answer[i]
is the number of words such that f(queries[i])
< f(W)
, where W
is a word in words
.
Example 1:
Input: queries = ["cbd"], words = ["zaaaz"]
Output: [1]
Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").
Example 2:
Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
Output: [1,2]
Explanation: On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").
Constraints:
1 <= queries.length <= 2000
1 <= words.length <= 2000
1 <= queries[i].length, words[i].length <= 10
queries[i][j]
,words[i][j]
are English lowercase letters.
int calculateFreq(string str) { // time: O(str_len)
char minChar = str[0];
int freq = 0;
for (char ch : str) {
if (ch == minChar) ++freq;
else if (ch < minChar) {
minChar = ch;
freq = 1;
}
}
return freq;
}
vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
// Preprocess for calculatino of the frequency of the smallest character in each word
vector<int> word_freq;
word_freq.reserve(words.size());
for (const string& word : words) {
word_freq.push_back(calculateFreq(word));
}
sort(word_freq.begin(), word_freq.end());
vector<int> res;
res.reserve(queries.size());
for (const string& query : queries) {
int freq = calculateFreq(query);
// Binary Search
// auto it = upper_bound(word_freq.begin(), word_freq.end(), freq);
// if (it == word_freq.end()) res.push_back(0);
// else res.push_back(word_freq.end() - it);
int l = 0, r = word_freq.size();
while (l < r) {
int mid = l + (r - l) / 2;
if (word_freq[mid] <= freq) l = mid + 1;
else r = mid;
}
res.push_back(word_freq.size() - l);
}
return res;
}
Last updated
Was this helpful?