1170. Compare Strings by Frequency of the Smallest Character
SourceWeekly Contest 151 Q2DifficultyMediumRating1431
Description
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.
Solutions
Solution 1: Sorting + Binary Search
Thinking
Each query counts how many \(\textit{words}\) have a strictly larger \(f\). Scanning all words per query is \(O(qn)\). Precompute every \(f(w)\), sort, and binary-search the first value above \(f(q)\); the suffix length is the answer. \(f\) is the count of the smallest letter and is linear in a short string.
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 \(\textit{words}\), sort them, and store them in an array \(\textit{nums}\).
Then, we traverse each string \(q\) in \(\textit{queries}\), and binary search in \(\textit{nums}\) for the first position \(i\) that is greater than \(f(q)\). Then, the elements at index \(i\) and after in \(\textit{nums}\) all satisfy \(f(q) < f(W)\), so the answer to the current query is \(n - i\).
The time complexity is \(O((n + q)M)\), and the space complexity is \(O(n)\), where \(n\) and \(q\) are the lengths of the arrays \(\textit{words}\) and \(\textit{queries}\) respectively, and \(M\) is the maximum length of the strings.
1 2 3 4 5 6 7 8 9 | |
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 28 29 30 31 32 33 34 35 36 37 38 39 | |
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 28 29 | |
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 | |
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 | |