# 1170. Compare Strings by Frequency of the Smallest Character

Let the function `f(s)` be the frequency of the lexicographically smallest character in a non-empty string `s`. For example, if `s = "dcce"` then `f(s) = 2` because the lexicographically smallest character is `'c'`, which has a frequency of 2.

You are given an array of strings `words` and another array of query strings `queries`. For each query `queries[i]`, count the number of words in `words` such that `f(queries[i])` < `f(W)` for each `W` in `words`.

Return  an integer array `answer` , where each  `answer[i]`  is the answer to the  `ith`  query.

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]` consist of lowercase English letters.

``````class Solution {
public:
vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
vector<int> res, freq;
for (string word : words) {
freq.push_back(f(word));
}
sort(freq.begin(), freq.end());
for (string query : queries) {
int cnt = f(query);
auto it = upper_bound(begin(freq), end(freq), cnt);
res.push_back(freq.end() - it);
}
return res;
}

int f(string s) {
sort(s.begin(), s.end());
for (int i = 0; i < s.size(); ++i) {
if (s[i] != s[0]) return i;
}
return s.size();
}
};
``````

``````class Solution {
public:
vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
vector<int> res, freq(12);
for (string word : words) {
++freq[f(word)];
}
for (int i = 9; i >= 0; --i) {
freq[i] += freq[i + 1];
}
for (string query : queries) {
int cnt = f(query);
res.push_back(freq[cnt + 1]);
}
return res;
}

int f(string s) {
sort(s.begin(), s.end());
for (int i = 0; i < s.size(); ++i) {
if (s[i] != s[0]) return i;
}
return s.size();
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1170

https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/

https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/discuss/366698/C%2B%2B-Keep-track-of-count-of-frequencies-Beats-100

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation