Algorithm
Problem Name: 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.
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 <= 20001 <= words.length <= 20001 <= queries[i].length, words[i].length <= 10queries[i][j],words[i][j]consist of lowercase English letters.
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const numSmallerByFrequency = function(queries, words) {
const qArr = []
for(let i = 0, len = queries.length; i < len; i++) {
let sm = 'z'
let hash = {}
let cur = queries[i]
for(let char of cur) {
if(hash[char] == null) hash[char] = 0
hash[char]++
if(char < sm) sm = char
}
qArr.push(hash[sm])
}
const wArr = []
for(let i = 0, len = words.length; i < len; i++) {
let sm = 'z'
let hash = {}
let cur = words[i]
for(let char of cur) {
if(hash[char] == null) hash[char] = 0
hash[char]++
if(char < sm) sm = char
}
wArr.push(hash[sm])
}
const res = []
for(let i = 0, len = queries.length; i < len; i++) {
let cur = 0
for(let j = 0, wlen = words.length; j < wlen; j++) {
if(qArr[i] < wArr[j]) cur++
}
res.push(cur>
}
return res
};
Input
Output
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
f = sorted(w.count(min(w)) for w in words)
return [len(f) - bisect.bisect(f, q.count(min(q))) for q in queries]
Input
Output
#3 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _1170_CompareStringsByFrequencyOfTheSmallestCharacter
{
public int[] NumSmallerByFrequency(string[] queries, string[] words)
{
var count = new int[12];
foreach (var word in words)
{
var charCount = new int[26];
var minChar = 26;
foreach (var ch in word)
{
var index = ch - 'a';
charCount[index]++;
if (index < minChar)
minChar = index;
}
count[charCount[minChar]]++;
}
for (int i = count.Length - 1; i > 0; i--)
count[i - 1] += count[i];
var result = new int[queries.Length];
var queryIndex = 0;
foreach (var query in queries)
{
var charCount = new int[26];
var minChar = 26;
foreach (var ch in query)
{
var index = ch - 'a';
charCount[index]++;
if (index < minChar)
minChar = index;
}
result[queryIndex++] = count[charCount[minChar] + 1];
}
return result;
}
}
}
Input
Output