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.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.
Java
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.
Java
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.
| 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. |
8 patterns to solve 80% Leetcode problems • Sahil & Sarra • 656,582 views views
Watch 9 more video solutions →Practice Compare Strings by Frequency of the Smallest Character with our built-in code editor and test cases.
Practice on FleetCode