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.

• Time : O(nlogm)
• Space : O(m)

class Solution {
    int f(string& s) {
        int cnt = 0;
        char ch = 'z' + 1;
        for(auto c : s) {
            if(c == ch) cnt++;
            else if(c < ch) {
                ch = c;
                cnt = 1;
            }
        }
        return cnt;
    }
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        vector<int> w(words.size());
        for(int i = 0; i < words.size(); i++) {
            w[i] = f(words[i]);
        }
        sort(w.begin(),w.end());
        
        vector<int> res(queries.size());
        for(int i = 0; i < queries.size(); i++) {
            int n = f(queries[i]);
            res[i] = w.end() - upper_bound(w.begin(),w.end(),n);
        }
        return res;
    }
};