Skip to content

1170. Compare Strings by Frequency of the Smallest Character 👎

  • Time:
  • Space:
 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
class Solution {
 public:
  vector<int> numSmallerByFrequency(vector<string>& queries,
                                    vector<string>& words) {
    vector<int> ans;
    vector<int> wordsFreq;

    for (const string& word : words)
      wordsFreq.push_back(f(word));
    sort(begin(wordsFreq), end(wordsFreq));

    for (const string& q : queries) {
      const int freq = f(q);
      ans.push_back(end(wordsFreq) -
                    upper_bound(begin(wordsFreq), end(wordsFreq), freq));
    }

    return ans;
  }

 private:
  int f(const string& word) {
    int count = 0;
    char currentChar = 'z' + 1;

    for (char c : word)
      if (c < currentChar) {
        currentChar = c;
        count = 1;
      } else if (c == currentChar)
        ++count;

    return count;
  }
};
 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
40
41
42
43
class Solution {
  public int[] numSmallerByFrequency(String[] queries, String[] words) {
    int[] ans = new int[queries.length];
    int[] wordsFreq = new int[words.length];

    for (int i = 0; i < words.length; ++i)
      wordsFreq[i] = f(words[i]);
    Arrays.sort(wordsFreq);

    for (int i = 0; i < queries.length; ++i) {
      final int freq = f(queries[i]);
      ans[i] = words.length - upper_bound(wordsFreq, 0, wordsFreq.length, freq);
    }

    return ans;
  }

  private int f(String word) {
    int count = 0;
    char currentChar = 'z' + 1;

    for (char c : word.toCharArray())
      if (c < currentChar) {
        currentChar = c;
        count = 1;
      } else if (c == currentChar) {
        ++count;
      }

    return count;
  }

  private int upper_bound(int[] nums, int l, int r, int value) {
    while (l < r) {
      final int m = (l + r) / 2;
      if (nums[m] <= value)
        l = m + 1;
      else
        r = m;
    }
    return l;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
  def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
    ans = []
    wordsFreq = sorted([word.count(min(word)) for word in words])

    for q in queries:
      count = q.count(min(q))
      index = bisect.bisect(wordsFreq, count)
      ans.append(len(words) - index)

    return ans