比较字符串最小字母出现频次 图解题解

f 到底数的是什么，这道题让我们求哪个数组

先把 f 说透：给一个字符串，找出字典序最小（a 比 b 小）的字母，数它出现几次就是 f。比如 f("dcce")=2（最小字母 c 出现 2 次），不是字母 c、也不是字母种类数。题目要对每个查询 q，数出 words 里有几个词 w 满足 f(q) 严格小于 f(w)。题面 queries=["bbb","cc"]、words=["a","aa","aaa","aaaa"] 答案 [1,2]。

每个查询都把所有词翻一遍，量大了要翻多少次

一个直接的想法：先把每个词的 f 算出来，再对每个查询把 n 个词的 f 挨个比、数出严格更大的有几个。算 f 跑不掉，开销压在数数上——一个查询扫 n 个词，m 个查询就是 O(n·m) 次比较。词和查询都几万时乘积上亿，每个查询都从头重数同一批词，全是重复劳动。

把词的 f 排好序，为什么每个查询就只剩一次二分

数「有几个比 x 大」其实不用一个个挨着数。先把所有词的 f 从小到大排成一排，比 x 大的数必然连成一段挤在右边。找到「第一个比 x 大的数」的位置，从那到末尾的个数就是答案。排序只做一次；之后每个查询在这排有序数里二分：靠有序，每回看中点砍掉一半，一次 O(log n)。一次 O(n log n) 预处理，换每次查询都快。

怎么二分出第一个严格更大的位置，中点比完往哪半收

要找「第一个严格大于 x 的位置」，对应 bisect_right（插入点落在等于 x 的数右边）。lo=0、hi=n 圈住范围，取中点 mid：sorted[mid] 大于 x，够格，但更靠左也许还有更小的也大于 x，hi 收到 mid；sorted[mid] 小于等于 x（等于不算，要严格更大），它和左边都不够大，lo 跳到 mid+1。缩到 lo、hi 撞上，那下标就是第一个更大的位置 p，答案 = n − p。

拿题面 bbb、cc 这组逐轮走二分

先算词的 f：f("a")=1、f("aa")=2、f("aaa")=3、f("aaaa")=4，排序 sorted=[1,2,3,4]，n=4。查询 "bbb" 的 f=3，从 lo=0、hi=4 起：mid=2、sorted[2]=3 不大于 3，lo=3；mid=3、sorted[3]=4 大于 3，hi=3；lo=hi=3，p=3，答案 4 − 3 = 1。查询 "cc" 的 f=2：mid=2、sorted[2]=3 大于 2，hi=2；mid=1、sorted[1]=2 不大于 2，lo=2；lo=hi=2，p=2，答案 4 − 2 = 2。合起来 [1,2]。

边界上最容易漏的：相等不算，跟一个都没有的时候

复杂度：算 f 共 O((n+m)·L)、排序 O(n log n)、查询二分 O(m log n)，空间 O(n)。「严格更大」最容易松手：f 相等的词不算，二分找第一个严格大于 x 的位置、而非大于等于，收缩时把 sorted[mid]=x 归到「不够大」那半（lo=mid+1），一松相等的就被错数进去。没有词比查询大时二分停在 p=n、答案 0；全都更大时 p=0、答案 n，两端都不必特判。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
from string import *
from operator import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
        def f(s: str) -> int:
            cnt = Counter(s)
            return next(cnt[c] for c in ascii_lowercase if cnt[c])

        n = len(words)
        nums = sorted(f(w) for w in words)
        return [n - bisect_right(nums, f(q)) for q in queries]

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        auto f = [](string s) {
            int cnt[26] = {0};
            for (char c : s) {
                cnt[c - 'a']++;
            }
            for (int x : cnt) {
                if (x) {
                    return x;
                }
            }
            return 0;
        };
        int n = words.size();
        int nums[n];
        for (int i = 0; i < n; i++) {
            nums[i] = f(words[i]);
        }
        sort(nums, nums + n);
        vector<int> ans;
        for (auto& q : queries) {
            int x = f(q);
            ans.push_back(n - (upper_bound(nums, nums + n, x) - nums));
        }
        return ans;
    }
};

Java

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int n = words.length;
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) {
            nums[i] = f(words[i]);
        }
        Arrays.sort(nums);
        int m = queries.length;
        int[] ans = new int[m];
        for (int i = 0; i < m; ++i) {
            int x = f(queries[i]);
            int l = 0, r = n;
            while (l < r) {
                int mid = (l + r) >> 1;
                if (nums[mid] > x) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            ans[i] = n - l;
        }
        return ans;
    }

    private int f(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            ++cnt[s.charAt(i) - 'a'];
        }
        for (int x : cnt) {
            if (x > 0) {
                return x;
            }
        }
        return 0;
    }
}