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.Problem Overview: Each string has a value f(s), defined as the frequency of its smallest character. For every query string, count how many words have a strictly larger f(s). The challenge is avoiding repeated comparisons across two lists of strings.
Approach 1: Naive Frequency Comparison (Brute Force) (Time: O(Q * W * L), Space: O(1))
Compute f(s) by scanning the string, finding the smallest character, then counting how many times it appears. For each query, iterate through every word and recompute f(word). If f(word) > f(query), increment the count. This approach uses simple iteration and string processing with no additional data structures. It works for small inputs but becomes slow because every comparison recomputes frequencies and scans the entire words array.
Approach 2: Precompute + Sorting with Binary Search (Time: O((Q + W) * L + W log W + Q log W), Space: O(W))
First compute f(word) for every word and store the values in an array. Sort this array. Now for each query, compute f(query) once and use binary search to find the first index where the stored frequency is greater than the query value. The number of valid words becomes len(wordsFreq) - index. Sorting enables logarithmic lookup instead of scanning the entire list each time. This technique combines preprocessing with efficient lookups using sorting and binary search.
Computing f(s) itself is straightforward: iterate over the string, track the smallest character, then count its occurrences. Since strings contain only lowercase letters, the operation runs in O(L) time where L is the string length. Problems like this often appear in interview sets focused on array processing and string analysis.
Recommended for interviews: The preprocessing + binary search approach. Interviewers expect you to notice repeated work in the brute force method and eliminate it by precomputing word frequencies. Sorting once and answering each query in logarithmic time demonstrates strong algorithmic thinking.
This approach involves calculating the frequency of the lexicographically smallest character for each query and each word. Then, for each query, we count how many words have a frequency greater than the frequency of the query.
This function computes f(s) for both queries and words, and compares the frequencies. It iterates over each query and calculates how many times the word frequency is greater than the query frequency.
Time Complexity: O(n * m) where n is the length of queries and m is the length of words.
Space Complexity: O(m) for storing words frequencies.
This approach first computes the frequency for all words and stores them in a list. Then, it sorts this list to enable binary search. For each query, we determine using binary search how many word frequencies are greater than the query frequency.
We compute and sort the frequency list of words and use binary search to find the position where the query's frequency would fit. The difference provides the count of higher frequencies.
Time Complexity: O(m log m + n log m) where n is the length of queries and m is the length of words.
Space Complexity: O(m) for storing sorted words frequencies.
First, according to the problem description, we implement a function f(s), which returns the frequency of the smallest letter in the string s in lexicographical order.
Next, we calculate f(w) for each string w in words, sort them, and store them in an array nums.
Then, we traverse each string q in queries, and binary search in nums for the first position i that is greater than f(q). Then, the elements at index i and after in nums all satisfy f(q) < f(W), so the answer to the current query is n - i.
The time complexity is O((n + q) times M), and the space complexity is O(n). Here, n and q are the lengths of the arrays words and queries respectively, and M is the maximum length of the strings.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Naive Approach | Time Complexity: O(n * m) where n is the length of queries and m is the length of words. |
| Optimized with Binary Search | Time Complexity: O(m log m + n log m) where n is the length of queries and m is the length of words. |
| Sorting + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Frequency Comparison | O(Q * W * L) | O(1) | Small datasets or when optimizing code simplicity over performance |
| Precompute + Sorting with Binary Search | O((Q + W) * L + W log W + Q log W) | O(W) | General case with many queries where repeated comparisons must be avoided |
1170 Compare Strings by Frequency of the Smallest Character • Kelvin Chandra • 2,657 views views
Watch 7 more video solutions →Practice Compare Strings by Frequency of the Smallest Character with our built-in code editor and test cases.
Practice on FleetCode