##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1170.html

# 1170. Compare Strings by Frequency of the Smallest Character (Easy)

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.

Related Topics:
Array, String

## Solution 1.

• class Solution {
public int[] numSmallerByFrequency(String[] queries, String[] words) {
int queriesLength = queries.length, wordsLength = words.length;
int[] queriesFrequency = new int[queriesLength];
int[] wordsFrequency = new int[wordsLength];
for (int i = 0; i < queriesLength; i++)
queriesFrequency[i] = frequency(queries[i]);
for (int i = 0; i < wordsLength; i++)
wordsFrequency[i] = frequency(words[i]);
int[] nums = new int[queriesLength];
for (int i = 0; i < queriesLength; i++) {
int queryFrequency = queriesFrequency[i];
for (int j = 0; j < wordsLength; j++) {
int wordFrequency = wordsFrequency[j];
if (queryFrequency < wordFrequency)
nums[i]++;
}
}
return nums;
}

public int frequency(String str) {
int[] count = new int[26];
char[] array = str.toCharArray();
for (char c : array)
count[c - 'a']++;
for (int i = 0; i < 26; i++) {
if (count[i] != 0)
return count[i];
}
return 0;
}
}

############

class Solution {
public int[] numSmallerByFrequency(String[] queries, String[] words) {
int n = words.length;
int[] arr = new int[n];
for (int i = 0; i < n; ++i) {
arr[i] = f(words[i]);
}
Arrays.sort(arr);
int m = queries.length;
int[] ans = new int[m];
for (int i = 0; i < m; ++i) {
int x = f(queries[i]);
ans[i] = n - search(arr, x);
}
return ans;
}

private int search(int[] arr, int x) {
int left = 0, right = arr.length;
while (left < right) {
int mid = (left + right) >> 1;
if (arr[mid] > x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}

private int f(String s) {
int[] cnt = new int[26];
for (int i = 0; i < s.length(); ++i) {
++cnt[s.charAt(i) - 'a'];
}
for (int v : cnt) {
if (v > 0) {
return v;
}
}
return 0;
}
}

• // OJ: https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/
// Time: O(W*Q)
// Space: O(W)
class Solution {
int frequency(string &s) {
int ch = 'z', cnt = 0;
for (char c : s) {
if (c < ch) {
cnt = 1;
ch = c;
} else if (c == ch) ++cnt;
}
return cnt;
}
public:
vector<int> numSmallerByFrequency(vector<string>& Q, vector<string>& W) {
vector<int> F(W.size()), ans;
for (int i = 0; i < W.size(); ++i) F[i] = frequency(W[i]);
for (auto &s : Q) {
int cnt = 0, f = frequency(s);
for (int i = 0; i < W.size(); ++i) cnt += F[i] > f;
ans.push_back(cnt);
}
return ans;
}
};

• class Solution:
def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
def f(s):
cnt = Counter(s)
for c in ascii_lowercase:
if cnt[c]:
return cnt[c]

arr = [f(s) for s in words]
arr.sort()
n = len(arr)
return [n - bisect_right(arr, f(q)) for q in queries]

############

# 1170. Compare Strings by Frequency of the Smallest Character
# https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/

class Solution:
def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
res, res1, res2 = [], [], []

def f(word):
count = [0] * 26
for w in word:
count[ord(w) - ord('a')] += 1

for c in count:
if c != 0: return c

return -1

for word in queries:
res1.append(f(word))

for word in words:
res2.append(f(word))

for x in res1:
count = 0
for y in res2:
if y > x:
count += 1

res.append(count)

return res


• func numSmallerByFrequency(queries []string, words []string) (ans []int) {
f := func(s string) int {
cnt := [26]int{}
for _, c := range s {
cnt[c-'a']++
}
for _, v := range cnt {
if v > 0 {
return v
}
}
return 0
}
arr := []int{}
for _, s := range words {
arr = append(arr, f(s))
}
sort.Ints(arr)
n := len(arr)
for _, q := range queries {
x := f(q)
ans = append(ans, n-sort.Search(n, func(i int) bool { return arr[i] > x }))
}
return
}

• function numSmallerByFrequency(queries: string[], words: string[]): number[] {
const f = (s: string): number => {
const cnt = new Array(26).fill(0);
for (const c of s) {
cnt[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
for (const x of cnt) {
if (x) {
return x;
}
}
return 0;
};
const nums: number[] = [];
for (const w of words) {
nums.push(f(w));
}
nums.sort((a, b) => a - b);
const ans: number[] = [];
for (const q of queries) {
const x = f(q);
let l = 0,
r = nums.length;
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] > x) {
r = mid;
} else {
l = mid + 1;
}
}
ans.push(nums.length - l);
}
return ans;
}