> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/string/1170.-compare-strings-by-frequency-of-the-smallest-character.md).

# 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.

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