# Compare Strings by Frequency of the Smallest Character
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character)
Canonical: https://scaleengineer.com/dsa/problems/compare-strings-by-frequency-of-the-smallest-character
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, String
---
## 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 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 <= 2000`
* `1 <= words.length <= 2000`
* `1 <= queries[i].length, words[i].length <= 10`
* `queries[i][j]`, `words[i][j]` consist of lowercase English letters.

# Approaches
## Brute Force Iteration
This approach directly translates the problem statement into code. For each query string, we iterate through all the words in the `words` array. In each inner iteration, we calculate the frequency of the smallest character for both the query string and the current word string and compare them.
**Time:** O(M * N * L), where `M` is the number of queries, `N` is the number of words, and `L` is the maximum length of a string. For each of the `M` queries, we iterate through `N` words, and for each pair, we call the `f` function which takes O(L) time. · **Space:** O(M) for the output array. If we exclude the output array, the auxiliary space is O(1) (the frequency map in `f` has a constant size of 26).
**Pros:** Simple to understand and implement.
**Cons:** Inefficient due to redundant calculations. The `f(word)` is recalculated for every query, leading to a high time complexity.
### Explanation
We'll need a helper function, let's call it `f(s)`, that takes a string `s` and returns the frequency of its lexicographically smallest character. To implement `f(s)`, we can use a frequency map (an array of size 26 for lowercase English letters). We iterate through the string `s` to populate this map. Then, we iterate through the map from index 0 to 25 (representing 'a' to 'z') and return the first non-zero frequency we find.

The main function will iterate through each `query` in the `queries` array. For each `query`, we first calculate its frequency, `f(query)`. Then, we start a nested loop to iterate through every `word` in the `words` array. Inside the nested loop, we calculate `f(word)`. If `f(query) < f(word)`, we increment a counter for the current query. After checking all words, the value of the counter is the result for the current query, which we store in our answer array. This process is repeated for all queries.

```java
class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int queryFreq = f(queries[i]);
            int count = 0;
            for (String word : words) {
                if (queryFreq < f(word)) {
                    count++;
                }
            }
            answer[i] = count;
        }
        return answer;
    }

    private int f(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }
        for (int count : counts) {
            if (count > 0) {
                return count;
            }
        }
        return 0;
    }
}
```
### Algorithm
- Initialize an integer array `answer` of the same size as `queries`.
- Define a helper function `f(s)` that calculates the frequency of the smallest character in `s`.
- Loop through each `query` at index `i` from `0` to `queries.length - 1`.
- Calculate `queryFreq = f(queries[i])`.
- Initialize a counter `count = 0`.
- Loop through each `word` in the `words` array.
- Calculate `wordFreq = f(word)`.
- If `queryFreq < wordFreq`, increment `count`.
- After the inner loop finishes, set `answer[i] = count`.
- Return `answer`.

## Pre-computation and Sorting with Binary Search
The brute-force approach is slow because it repeatedly calculates the frequencies for the `words` array. We can optimize this by pre-calculating all these frequencies once and storing them. Then, for each query, we can efficiently find the number of words with a higher frequency by sorting the pre-calculated frequencies and using binary search.
**Time:** O(N*L + N*log(N) + M*(L + log(N))), where M is `queries.length`, N is `words.length`, and L is max string length. This is composed of O(N*L) to compute all word frequencies, O(N*log(N)) to sort them, and O(M*(L + log(N))) to process all queries. · **Space:** O(N + M). O(N) for `wordFreqs` and O(M) for the output array.
**Pros:** Much more efficient than brute force, especially for a large number of queries and words.; Avoids redundant computations by pre-calculating word frequencies.
**Cons:** Sorting can be overkill if the range of frequencies is small, as is the case in this problem.
### Explanation
First, we create an integer array, say `wordFreqs`, with the same size as the `words` array. We iterate through the `words` array once, calculate `f(word)` for each `word`, and store the result in `wordFreqs`. This avoids redundant calculations. To quickly count how many words have a frequency greater than a query's frequency, we can sort the `wordFreqs` array in ascending order.

Now, for each `query`, we calculate its frequency, `q_freq`. We then perform a binary search on the sorted `wordFreqs` array to find the index of the first element that is strictly greater than `q_freq`. If such an element is found at index `k`, then all elements from `k` to the end of the array (`wordFreqs.length - 1`) will also be greater than `q_freq`. The number of such elements is `wordFreqs.length - k`. This is the answer for the current query. If no such element is found, it means all word frequencies are less than or equal to `q_freq`, so the answer is 0.

```java
import java.util.Arrays;

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] wordFreqs = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            wordFreqs[i] = f(words[i]);
        }
        Arrays.sort(wordFreqs);

        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int queryFreq = f(queries[i]);
            // Binary search to find first element > queryFreq
            int left = 0, right = wordFreqs.length - 1;
            int firstGreaterIndex = wordFreqs.length;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (wordFreqs[mid] > queryFreq) {
                    firstGreaterIndex = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            answer[i] = wordFreqs.length - firstGreaterIndex;
        }
        return answer;
    }

    private int f(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }
        for (int count : counts) {
            if (count > 0) {
                return count;
            }
        }
        return 0;
    }
}
```
### Algorithm
- Define a helper function `f(s)` as in the previous approach.
- Create an integer array `wordFreqs` of size `words.length`.
- Iterate through the `words` array, and for each `word` at index `j`, compute `wordFreqs[j] = f(words[j])`.
- Sort the `wordFreqs` array.
- Initialize an integer array `answer` of size `queries.length`.
- Loop through each `query` at index `i` from `0` to `queries.length - 1`.
- Calculate `queryFreq = f(queries[i])`.
- Perform a binary search on `wordFreqs` to find the number of elements greater than `queryFreq`. This can be done by finding the index of the first element strictly greater than `queryFreq`. Let this index be `k`.
- The count is `wordFreqs.length - k`.
- Store this count in `answer[i]`.
- Return `answer`.

## Pre-computation and Frequency Counting
This is the most optimal approach, which leverages the problem's constraints. The maximum length of any string is 10, which means the frequency `f(s)` can be at most 10. Since the range of possible frequencies is very small (1 to 10), we can use a frequency array (similar to counting sort) instead of a general sort and binary search.
**Time:** O(N*L + M*L), where M is `queries.length`, N is `words.length`, and L is max string length. This consists of O(N*L) to compute all word frequencies, O(1) to compute suffix sums, and O(M*L) to process all queries. · **Space:** O(M). O(1) for `freqCounts` (constant size 12) and O(M) for the output array.
**Pros:** The most efficient solution due to constant time lookups for each query after pre-computation.; Effectively utilizes the problem's constraints on string length.
**Cons:** Slightly more complex to reason about due to the frequency-of-frequencies and suffix sum concepts.
### Explanation
First, we observe that the maximum length of any word is 10. This implies the maximum possible frequency of the smallest character is also 10. We create a frequency-of-frequencies array, let's call it `freqCounts`, of size 12 (to handle frequencies from 0 to 11, providing a safe buffer). `freqCounts[k]` will store the number of words in the `words` array that have a frequency `f(word) = k`. We iterate through the `words` array, calculate `f(word)` for each word, and increment the corresponding counter in `freqCounts`.

To efficiently answer the queries, we need to find the total count of words whose frequency is greater than a given `q_freq`. This is the sum of `freqCounts[k]` for all `k > q_freq`. Instead of summing this up for each query, we can pre-calculate a suffix sum on `freqCounts`. We can update `freqCounts` in place to store these suffix sums. We iterate from right to left (from index 10 down to 0) and update `freqCounts[i] = freqCounts[i] + freqCounts[i+1]`. After this, `freqCounts[i]` will store the number of words with frequency `f(word) >= i`.

Finally, we iterate through the `queries`. For each `query`, we calculate `q_freq = f(query)`. The number of words `W` with `f(W) > q_freq` is the same as the number of words with `f(W) >= q_freq + 1`. This value is readily available in our pre-computed suffix sum array at index `q_freq + 1`. This lookup takes O(1) time for each query.

```java
class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        // Max frequency is 10 (max string length). Array size 12 for safety (indices 0-11).
        int[] freqCounts = new int[12];
        for (String word : words) {
            freqCounts[f(word)]++;
        }

        // Calculate suffix sums. freqCounts[i] will store count of words with frequency >= i.
        for (int i = 10; i >= 0; i--) {
            freqCounts[i] += freqCounts[i + 1];
        }

        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int queryFreq = f(queries[i]);
            // We need count of words with frequency > queryFreq.
            // This is equivalent to count of words with frequency >= queryFreq + 1.
            answer[i] = freqCounts[queryFreq + 1];
        }
        return answer;
    }

    private int f(String s) {
        int[] counts = new int[26];
        for (char c : s.toCharArray()) {
            counts[c - 'a']++;
        }
        for (int count : counts) {
            if (count > 0) {
                return count;
            }
        }
        return 0;
    }
}
```
### Algorithm
- Define a helper function `f(s)` as before.
- Create an integer array `freqCounts` of size 12, initialized to zeros.
- Iterate through the `words` array. For each `word`, calculate its frequency `w_freq = f(word)` and increment `freqCounts[w_freq]`.
- Compute the suffix sums for `freqCounts`. Iterate from `i = 10` down to `0`: `freqCounts[i] += freqCounts[i+1]`.
- Initialize an integer array `answer` of size `queries.length`.
- Loop through each `query` at index `i`.
- Calculate `queryFreq = f(queries[i])`.
- The number of words with frequency greater than `queryFreq` is `freqCounts[queryFreq + 1]`.
- Set `answer[i] = freqCounts[queryFreq + 1]`.
- Return `answer`.

# Solutions
### Java

```java
class Solution { public int [] numSmallerByFrequency ( String [] queries , String [] words ) { int n = words . length ; int [] nums = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { nums [ i ] = f ( words [ i ]); } Arrays . sort ( nums ); int m = queries . length ; int [] ans = new int [ m ]; for ( int i = 0 ; i < m ; ++ i ) { int x = f ( queries [ i ]); int l = 0 , r = n ; while ( l < r ) { int mid = ( l + r ) >> 1 ; if ( nums [ mid ] > x ) { r = mid ; } else { l = mid + 1 ; } } ans [ i ] = n - l ; } return ans ; } 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 x : cnt ) { if ( x > 0 ) { return x ; } } return 0 ; } }
```

### CPP

```cpp
class Solution { public: vector < int > numSmallerByFrequency ( vector < string >& queries , vector < string >& words ) { auto f = []( string s ) { int cnt [ 26 ] = { 0 }; for ( char c : s ) { cnt [ c - 'a' ] ++ ; } for ( int x : cnt ) { if ( x ) { return x ; } } return 0 ; }; int n = words . size (); int nums [ n ]; for ( int i = 0 ; i < n ; i ++ ) { nums [ i ] = f ( words [ i ]); } sort ( nums , nums + n ); vector < int > ans ; for ( auto & q : queries ) { int x = f ( q ); ans . push_back ( n - ( upper_bound ( nums , nums + n , x ) - nums )); } return ans ; } };
```

### Python

```python
class Solution : def numSmallerByFrequency ( self , queries : List [ str ], words : List [ str ]) -> List [ int ]: def f ( s : str ) -> int : cnt = Counter ( s ) return next ( cnt [ c ] for c in ascii_lowercase if cnt [ c ]) n = len ( words ) nums = sorted ( f ( w ) for w in words ) return [ n - bisect_right ( nums , f ( q )) for q in queries ]
```