Leetcode 1170. Compare Strings by Frequency of the Smallest Character
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 onlyf("aaaa")=2
, thus there is only 1 string inwords
where the frequency of the smallest character is larger than that inqueries
. -
For the second query,
f("cc")=2
. Here,f("aaa")=3
andf("aaaa")=4
so that's 2 words inwords
with a larger frequency of smallest character thanf("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:
-
First, create a helper function to calculate the frequency of the smallest character in a string as described above.
-
Create an array,
wordsFreq
, to store the frequencies of smallest characters inwords
. -
Then, sort
wordsFreq
in ascending order. -
Loop through each query in
queries
, calculate its frequency, and compare it towordsFreq
. We increment the count for each frequency inwordsFreq
that is larger than the frequency inquery
. -
Use the built-in
upper_bound
function to quickly find the number of frequencies inwordsFreq
larger than our current frequency. This function returns an iterator to the first element in the range[first, last)
that is greater thanvalue
, or last if no such element is found. -
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:
-
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, ands.count(min(s))
will return the count of the smallest character. -
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 calculatef(query)
and add the count of all words with largerf(word)
directly from our count array. -
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.
-
C++ Version: C++ version makes use of the STL algorithm functions like
sort()
,count()
, andupper_bound()
. The functionmicroHelper
calculates the frequency of the smallest character in a string. -
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 largerf(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.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.