Watch 8 video solutions for Compare Strings by Frequency of the Smallest Character, a medium level problem involving Array, Hash Table, String. This walkthrough by Kelvin Chandra has 2,657 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |