1170. Compare Strings by Frequency of the Smallest Character LeetCode Solution
In this guide, you will get 1170. Compare Strings by Frequency of the Smallest Character LeetCode Solution with the best time and space complexity. The solution to Compare Strings by Frequency of the Smallest Character problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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.
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(“cc”).
1170. Compare Strings by Frequency of the Smallest Character LeetCode Solution in C++
class Solution {
public:
vector<int> numSmallerByFrequency(vector<string>& queries,
vector<string>& words) {
vector<int> ans;
vector<int> wordsFreq;
for (const string& word : words)
wordsFreq.push_back(f(word));
ranges::sort(wordsFreq);
for (const string& query : queries) {
const int freq = f(query);
ans.push_back(wordsFreq.end() - ranges::upper_bound(wordsFreq, freq));
}
return ans;
}
private:
int f(const string& word) {
int count = 0;
char currentChar = 'z' + 1;
for (const char c : word)
if (c < currentChar) {
currentChar = c;
count = 1;
} else if (c == currentChar) {
++count;
}
return count;
}
}; /* code provided by PROGIEZ */
1170. Compare Strings by Frequency of the Smallest Character LeetCode Solution in Java
class Solution {
public int[] numSmallerByFrequency(String[] queries, String[] words) {
int[] ans = new int[queries.length];
int[] wordsFreq = new int[words.length];
for (int i = 0; i < words.length; ++i)
wordsFreq[i] = f(words[i]);
Arrays.sort(wordsFreq);
for (int i = 0; i < queries.length; ++i) {
final int freq = f(queries[i]);
ans[i] = words.length - firstGreater(wordsFreq, 0, wordsFreq.length, freq);
}
return ans;
}
private int f(final String word) {
int count = 0;
char currentChar = 'z' + 1;
for (final char c : word.toCharArray())
if (c < currentChar) {
currentChar = c;
count = 1;
} else if (c == currentChar) {
++count;
}
return count;
}
private int firstGreater(int[] nums, int l, int r, int value) {
while (l < r) {
final int m = (l + r) / 2;
if (nums[m] > value)
r = m;
else
l = m + 1;
}
return l;
}
} // code provided by PROGIEZ
1170. Compare Strings by Frequency of the Smallest Character LeetCode Solution in Python
class Solution:
def numSmallerByFrequency(
self,
queries: list[str],
words: list[str],
) -> list[int]:
ans = []
wordsFreq = sorted([word.count(min(word)) for word in words])
for q in queries:
count = q.count(min(q))
index = bisect.bisect(wordsFreq, count)
ans.append(len(words) - index)
return ans # code by PROGIEZ
