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;
}