---
title: leetcode 1170
tags: leetcode, binary search
---

// https://leetcode.com/problems/compare-strings-by-frequency-of-the-smallest-character/
class Solution {
private:
  int fw[2000];
  int cal(string s) {
    int ary[26] = {0};
    for (int i=0; i<s.length(); i++) {
      ary[s[i] - 'a']++;
    }
    for (int i=0; i<26; i++)
      if (ary[i]) return ary[i];
    return 0;
  }
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
      for (int i=0; i<words.size(); i++)
        fw[i] = cal(words[i]);
      sort(fw, fw+queries.size());
      vector<int> ans;
      for (int i=0; i<queries.size(); i++) {
        int fq = cal(queries[i]);
        ans.push_back(words.size() - (upper_bound(fw, fw+words.size(), fq) - fw));
      }
      return ans;
    }
};