Problem Explanation

This problem requires you to create a function f(s) which calculates the frequency of the smallest character in a string s. For example, if s = "dcce" then f(s) = 2 because the smallest character is "c" and its frequency is 2.

After creating this function, you're given two arrays of strings: queries and words. This function needs to return an integer array, answer, where each answer[i] is the number of words such, where f(queries[i]) is less than f(W), with W being a word from the words array.

For example, given queries = ["bbb","cc"] and words = ["a","aa","aaa","aaaa"], the output would be [1,2]. The reasons are as follows:

• For the first query, f("bbb")=3 and only f("aaaa")=2, thus there is only 1 string in words where the frequency of the smallest character is larger than that in queries.

• For the second query, f("cc")=2. Here, f("aaa")=3 and f("aaaa")=4 so that's 2 words in words with a larger frequency of smallest character than f("cc").

The problem constraints indicate that the sizes of queries and words are from 1 to 2000 and the lengths of the strings in these arrays are between 1 and 10. All characters in these strings are English lowercase.

Problem Approach

For finding a solution to this problem, we'll follow these steps:

1. First, create a helper function to calculate the frequency of the smallest character in a string as described above.

2. Create an array, wordsFreq, to store the frequencies of smallest characters in words.

3. Then, sort wordsFreq in ascending order.

4. Loop through each query in queries, calculate its frequency, and compare it to wordsFreq. We increment the count for each frequency in wordsFreq that is larger than the frequency in query.

5. Use the built-in upper_bound function to quickly find the number of frequencies in wordsFreq larger than our current frequency. This function returns an iterator to the first element in the range [first, last) that is greater than value, or last if no such element is found.

6. Store the total count in the ans array.

Let's proceed to write the solution in multiple languages:

Python

1
2python
3class Solution:
4    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
5        def f(s):
6            return s.count(min(s))
7
8        words = sorted(map(f, words))
9        return [len(words) - bisect.bisect(words, f(query)) for query in queries]

Java

1
2java
3class Solution {
4    public int[] numSmallerByFrequency(String[] queries, String[] words) {
5        int[] wordCount = new int[12];
6        for (String word : words) {
7            wordCount[f(word)]++;
8        }
9        for (int i = 9; i >= 0; i--) {
10            wordCount[i] += wordCount[i + 1];
11        }
12        
13        int[] result = new int[queries.length];
14        for (int i = 0; i < queries.length; i++) {
15            result[i] = wordCount[f(queries[i]) + 1];
16        }
17        return result;
18    }
19    private int f(String s) {
20        int[] counter = new int[26];
21        for (char c : s.toCharArray()) {
22            counter[c - 'a']++;
23        }
24        for (int count : counter) {
25            if (count != 0) return count;
26        }
27        return 0;
28    }
29}

JavaScript

1
2javascript
3var numSmallerByFrequency = function(queries, words) {
4    let ans = new Array(queries.length).fill(0);
5    let wordsArrSortedByCount = words.map(w => [...w].sort((a, b) => a.localeCompare(b)).join('')).map(w=>w.lastIndexOf(w[0])+1).sort((a, b) => a - b);
6    queries.map(q => [...q].sort((a, b) => a.localeCompare(b)).join('')).map((q, i) => ans[i] = wordsArrSortedByCount.filter(w => w > q.lastIndexOf(q[0])+1).length)
7    return ans
8};

C++

1
2c++
3class Solution {
4public:
5    int microHelper(string s) {
6        sort(s.begin(), s.end());
7        return count(s.begin(), s.end(), s[0]);
8    }
9    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
10        vector<int> res, words_micro;
11        for(string word : words) words_micro.push_back(microHelper(word));
12        for(string que : queries)
13            res.push_back(words_micro.end() - upper_bound(words_micro.begin(), words_micro.end(), microHelper(que)));
14        return res;
15    }
16};

C#

1
2csharp
3public class Solution {
4    public int[] NumSmallerByFrequency(string[] queries, string[] words) {
5        int[] wordCount = new int[12];
6        foreach (string word in words) {
7            wordCount[f(word)]++;
8        }
9        for (int i = 9; i >= 0; i--) {
10            wordCount[i] += wordCount[i + 1];
11        }
12        
13        int[] result = new int[queries.Length];
14        for (int i = 0; i < queries.Length; i++) {
15            result[i] = wordCount[f(queries[i]) + 1];
16        }
17        return result;
18    }
19    private int f(String s) {
20        int[] counter = new int[26];
21        foreach (char c in s.ToCharArray()) {
22            counter[c - 'a']++;
23        }
24        foreach (int count in counter) {
25            if (count != 0) return count;
26        }
27        return 0;
28    }
29}

Every language solution above provides the correct result, but each one has a slightly different approach due to the language differences:

1. Python Version: The Python solution is probably the most simplified version of all, thanks to Python's incredible syntax. In the function f, min(s) will always return the smallest character in the string, and s.count(min(s)) will return the count of the smallest character.

2. Java Version: The Java solution is slightly different, here the frequencies are stored in an array wordCount and we keep the cumulative sum of counts in the array. Then, for each query, we calculate f(query) and add the count of all words with larger f(word) directly from our count array.

3. JavaScript Version: The JavaScript solution maps every word in queries and words to an array then sorts them in lexicographical order. Then it maps the count of minimal character in each query and compares it with those of every word in words array.

4. C++ Version: C++ version makes use of the STL algorithm functions like sort(), count(), and upper_bound(). The function microHelper calculates the frequency of the smallest character in a string.

5. C# Version: The C# solution is quite similar to Java's. Here also frequencies of smallest characters are stored in an array, wordCount and a cumulative sum of counts is stored in the array. For every word with larger f(word) in our count array, we add the count directly to our result for each query.

This problem showcases the use of keeping count and cumulative sums for frequency related problems irrespective of the choice of language. It also emphasizes the use of helper functions thus maintaining the DRY (Don't Repeat Yourself) principle.