|
2 | 2 |
|
3 | 3 | import java.util.Arrays;
|
4 | 4 |
|
5 |
| -/** |
6 |
| - * 1170. Compare Strings by Frequency of the Smallest Character |
7 |
| - * |
8 |
| - * Let's define a function f(s) over a non-empty string s, |
9 |
| - * which calculates the frequency of the smallest character in s. |
10 |
| - * For example, if s = "dcce" then f(s) = 2 because the smallest character is "c" and its frequency is 2. |
11 |
| - * Now, given string arrays queries and words, |
12 |
| - * return an integer array answer, |
13 |
| - * where each answer[i] is the number of words such that f(queries[i]) < f(W), where W is a word in words. |
14 |
| - * |
15 |
| - * Example 1: |
16 |
| - * Input: queries = ["cbd"], words = ["zaaaz"] |
17 |
| - * Output: [1] |
18 |
| - * Explanation: On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz"). |
19 |
| - * |
20 |
| - * Example 2: |
21 |
| - * Input: queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"] |
22 |
| - * Output: [1,2] |
23 |
| - * Explanation: On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc"). |
24 |
| - * |
25 |
| - * Constraints: |
26 |
| - * 1 <= queries.length <= 2000 |
27 |
| - * 1 <= words.length <= 2000 |
28 |
| - * 1 <= queries[i].length, words[i].length <= 10 |
29 |
| - * queries[i][j], words[i][j] are English lowercase letters. |
30 |
| - * */ |
31 | 5 | public class _1170 {
|
32 | 6 | public static class Solution1 {
|
33 | 7 | /**
|
34 | 8 | * Use simple iteration when finding counts
|
35 | 9 | * Time: O(n^m) where m is the size of queries and n is the size of words
|
36 | 10 | * Space: O(max(m, n) where m is the size of queries and n is the size of words)
|
37 |
| - * */ |
| 11 | + */ |
38 | 12 | public int[] numSmallerByFrequency(String[] queries, String[] words) {
|
39 | 13 | int[] queriesMinFrequecies = new int[queries.length];
|
40 | 14 | for (int i = 0; i < queries.length; i++) {
|
@@ -87,7 +61,7 @@ public static class Solution2 {
|
87 | 61 | * Use binary search when finding counts
|
88 | 62 | * Time: O(n^logn) where m is the size of queries and n is the size of words
|
89 | 63 | * Space: O(max(m, n) where m is the size of queries and n is the size of words)
|
90 |
| - * */ |
| 64 | + */ |
91 | 65 | public int[] numSmallerByFrequency(String[] queries, String[] words) {
|
92 | 66 | int[] queriesMinFrequecies = new int[queries.length];
|
93 | 67 | for (int i = 0; i < queries.length; i++) {
|
|
0 commit comments