Skip to content

1170. Compare Strings by Frequency of the Smallest Character 👎

  • Time: $O(\texttt{sort})$
  • Space: $O(\texttt{sort})$
 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));
    ranges::sort(wordsFreq);

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

    return ans;
  }

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

    for (const 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 - firstGreater(wordsFreq, 0, wordsFreq.length, freq);
    }

    return ans;
  }

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

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

    return count;
  }

  private int firstGreater(int[] nums, int l, int r, int value) {
    while (l < r) {
      final int m = (l + r) / 2;
      if (nums[m] > value)
        r = m;
      else
        l = m + 1;
    }
    return l;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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