Problem

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 arrayanswer , where eachanswer[i]is the answer to theith query.

Examples

Example 1

1
2
3

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

1
2
3

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] consist of lowercase English letters.

Solution

Method 1 – Frequency Counting and Binary Search

Intuition

For each word, compute the frequency of its smallest character. Sort these frequencies. For each query, compute its smallest character frequency and count how many word frequencies are greater using binary search.

Approach

  1. Define a function to compute the frequency of the smallest character in a string.
  2. Compute and sort the frequencies for all words.
  3. For each query, compute its frequency and use binary search to count how many word frequencies are greater.
  4. Return the result for all queries.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int f(const string& s) {
        char mn = 'z'; int cnt = 0;
        for (char c : s) {
            if (c < mn) mn = c, cnt = 1;
            else if (c == mn) cnt++;
        }
        return cnt;
    }
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        vector<int> ws;
        for (auto& w : words) ws.push_back(f(w));
        sort(ws.begin(), ws.end());
        vector<int> ans;
        for (auto& q : queries) {
            int fq = f(q);
            ans.push_back(ws.end() - upper_bound(ws.begin(), ws.end(), fq));
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func numSmallerByFrequency(queries, words []string) []int {
    f := func(s string) int {
        mn, cnt := byte('z'), 0
        for i := 0; i < len(s); i++ {
            if s[i] < mn { mn, cnt = s[i], 1 }
            else if s[i] == mn { cnt++ }
        }
        return cnt
    }
    ws := make([]int, len(words))
    for i, w := range words { ws[i] = f(w) }
    sort.Ints(ws)
    ans := make([]int, len(queries))
    for i, q := range queries {
        fq := f(q)
        l, r := 0, len(ws)
        for l < r {
            m := (l + r) / 2
            if ws[m] <= fq { l = m + 1 } else { r = m }
        }
        ans[i] = len(ws) - l
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    int f(String s) {
        char mn = 'z'; int cnt = 0;
        for (char c : s.toCharArray()) {
            if (c < mn) { mn = c; cnt = 1; }
            else if (c == mn) cnt++;
        }
        return cnt;
    }
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] ws = new int[words.length];
        for (int i = 0; i < words.length; i++) ws[i] = f(words[i]);
        Arrays.sort(ws);
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int fq = f(queries[i]);
            int l = 0, r = ws.length;
            while (l < r) {
                int m = (l + r) / 2;
                if (ws[m] <= fq) l = m + 1;
                else r = m;
            }
            ans[i] = ws.length - l;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    fun numSmallerByFrequency(queries: Array<String>, words: Array<String>): IntArray {
        fun f(s: String): Int {
            var mn = 'z'; var cnt = 0
            for (c in s) {
                if (c < mn) { mn = c; cnt = 1 }
                else if (c == mn) cnt++
            }
            return cnt
        }
        val ws = words.map { f(it) }.sorted()
        return queries.map { q ->
            val fq = f(q)
            var l = 0; var r = ws.size
            while (l < r) {
                val m = (l + r) / 2
                if (ws[m] <= fq) l = m + 1 else r = m
            }
            ws.size - l
        }.toIntArray()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def numSmallerByFrequency(self, queries: list[str], words: list[str]) -> list[int]:
        def f(s: str) -> int:
            mn = min(s)
            return s.count(mn)
        ws = sorted(f(w) for w in words)
        ans = []
        for q in queries:
            fq = f(q)
            l, r = 0, len(ws)
            while l < r:
                m = (l + r) // 2
                if ws[m] <= fq:
                    l = m + 1
                else:
                    r = m
            ans.append(len(ws) - l)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn num_smaller_by_frequency(queries: Vec<String>, words: Vec<String>) -> Vec<i32> {
        fn f(s: &str) -> i32 {
            let mn = s.chars().min().unwrap();
            s.chars().filter(|&c| c == mn).count() as i32
        }
        let mut ws: Vec<i32> = words.iter().map(|w| f(w)).collect();
        ws.sort();
        queries.iter().map(|q| {
            let fq = f(q);
            let l = ws.partition_point(|&x| x <= fq);
            (ws.len() - l) as i32
        }).collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
    numSmallerByFrequency(queries: string[], words: string[]): number[] {
        function f(s: string): number {
            const mn = s.split('').reduce((a, b) => a < b ? a : b);
            return s.split('').filter(c => c === mn).length;
        }
        const ws = words.map(f).sort((a, b) => a - b);
        return queries.map(q => {
            const fq = f(q);
            let l = 0, r = ws.length;
            while (l < r) {
                const m = (l + r) >> 1;
                if (ws[m] <= fq) l = m + 1; else r = m;
            }
            return ws.length - l;
        });
    }
}

Complexity

  • ⏰ Time complexity: O((n + m) log m), where n = len(queries), m = len(words).
  • 🧺 Space complexity: O(m)