LeetCode 1170. 比较字符串最小字母出现频次

2023-06-10 HGNULB 约 11 分钟

文章信息 6 个分类 5 个标签

分类

题目描述

✅ 1170. 比较字符串最小字母出现频次

题意分析

定义函数 $f(s)$ 为「字符串 s 中字典序最小的那个字母出现的次数」。例如 $f(\texttt{"dcce"}) = 2$，因为最小字母是 c，出现两次。给定 queries 与 words 两个字符串数组，对每个 queries[i]，统计 words 中有多少个 w 满足 $f(\texttt{queries[i]}) < f(w)$，把结果按顺序返回。

读题的第一个陷阱在 $f$ 的定义：它数的是最小字母的出现次数，不是最小的出现次数，也不是字符串长度或去重后的字符数。"aabbb" 的最小字母是 a，$f = 2$（不是 3）。把这个定义翻译准确，题目就成功了一半。

第二个要点是：一旦所有字符串都被 $f$ 压成一个整数，原始字符串就再也不需要了。问题瞬间退化成「给一组数 A 和一组数 B，对每个 $b \in B$ 求 A 中严格大于 $b$ 的元素个数」——这是一个纯粹的计数问题，与字符串毫无关系。识别出这一步「降维」是解题的关键转折。

约束：两个数组长度都不超过 2000，每个字符串长度不超过 10。乍看 $2000 \times 2000 = 4 \times 10^6$ 的暴力两两比较也能过，但这个规模同时也允许把它做得更漂亮——而且更重要的是，$f$ 的值域被字符串长度限死在 $[1, 10]$ 这个极小的区间里，这个信息暗示了不止一种优化路径。

边界：words 中可能没有任何一个 $f$ 值大于某个查询，答案为 0；也可能全部大于，答案为 words.length；比较是严格大于，$f$ 相等不计入。

解法：统计最小字符频次 + 二分

核心思路

先看暴力：对每个查询都扫描全部 words，即使每个字符串的 $f$ 只计算一次，也需要 $O(mn)$ 次数值比较；若在内层重复计算 $f(w)$，还会重复扫描单词字符。瓶颈有两处：相同单词被重复求频次，以及每个查询都要线性扫描全部单词。

第一个瓶颈的修复是显然的：预处理，把 words 一次性映射成整数数组 freqWords，此后只跟数字打交道。

第二个瓶颈需要一点结构。「统计数组中大于某值的元素个数」这个操作，如果数组是有序的，就可以用二分把 $O(n)$ 降到 $O(\log n)$：先找到第一个大于目标值的位置 idx，那么从 idx 到末尾的所有元素都严格大于目标，个数就是 n - idx。

所以整个算法是三段式：

words → freqWords（每个元素是一个 $f$ 值），排序；

对每个查询算出 $f(q)$；

在 freqWords 上二分求 upperBound(q)，答案是 n - idx。

这里的不变量是：freqWords 始终保持升序，upperBound(q) 返回的是「第一个满足 freqWords[idx] > q 的下标」（若不存在则返回 n）。有了这个定义，n - idx 恰好就是严格大于 q 的元素个数，不需要任何加一减一的调整——这正是选 upperBound 而不是 lowerBound 的原因：题目要的是严格大于，lowerBound 找的是第一个「大于等于」的位置，会把 $f$ 值相等的词错误地算进去。

$f$ 的计算本身也值得说。一次遍历同时维护「当前见过的最小字母 min」和「它的出现次数 count」：遇到比 min 更小的字符，说明之前统计的最小字母作废，把 min 换成新字符并把 count 重置为 1；遇到等于 min 的字符，count++；比 min 大的直接忽略。min 初值取 'z'——它是可能出现的最大字母，保证第一个字符一定能触发「更小」分支（或在字符恰为 'z' 时触发「相等」分支），两种情况都能正确起步。这个一次遍历的写法比「先求最小值再数一遍」少扫一趟，也比开 26 个桶更简洁。

正确性：扫描字符串时，min 与 count 始终是已扫描前缀的最小字母及其频次，因此预处理得到的每个 $f$ 值准确。排序后，upperBound(q) 左侧全部不大于 $q$，右侧全部严格大于 $q$；所以 n - idx 不多不少地统计了满足条件的单词。逐查询应用该结论，返回数组正确。

解题步骤

预处理 words 的 $f$ 值：遍历 words 逐个调用 minCharFreq，存进 freqWords。每个单词只扫描一次，避免在不同查询中重复计算。

排序 freqWords：二分的前置条件。注意排序后 freqWords 与原 words 的对应关系被打乱了——但题目只要计数、不要具体是哪些词，所以可以放心排序。

对每个查询算 $f(q)$：同一个 minCharFreq 复用。

二分求第一个大于 q 的下标：left = 0、right = n（开区间右端，取 n 而不是 n - 1，这样「全部元素都不大于 q」时能自然返回 n）；循环条件 left < right；mid = left + (right - left) / 2 避免加法溢出；判断 arr[mid] <= target 时说明答案在右边，left = mid + 1，否则 right = mid（mid 本身可能就是答案，不能跳过）。循环结束时 left == right，即为所求。

计数：res[i] = freqWords.length - idx。因为数组升序且 idx 是第一个大于 q 的位置，其后所有元素必然也大于 q。

返回 res，长度与 queries 一致、顺序一一对应。

以 queries = ["bbb", "cc"]、words = ["a", "aa", "aaa", "aaaa"] 走一遍（答案 [1, 2]）：

先算 words 的 $f$ 值："a" 最小字母 a 出现 1 次 → 1；"aa" → 2；"aaa" → 3；"aaaa" → 4。freqWords = [1, 2, 3, 4]，已经有序。

处理 "bbb"：minCharFreq 从 min = 'z' 开始，第一个字符 b < z，min = 'b'、count = 1；后两个 b 都等于 min，count 增到 3。$f = 3$。
二分 upperBound([1,2,3,4], 3)：left = 0, right = 4 → mid = 2，arr[2] = 3 <= 3，left = 3；left = 3, right = 4 → mid = 3，arr[3] = 4 > 3，right = 3；left == right == 3 退出。idx = 3，答案 4 - 3 = 1——只有 "aaaa" 的 $f = 4 > 3$。

注意这里若用 lowerBound（第一个 >= 3 的位置 = 2），答案会算成 4 - 2 = 2，把 $f$ 同为 3 的 "aaa" 错误地计入——严格大于与大于等于的一字之差，就体现在这一个下标上。

处理 "cc"：最小字母 c 出现 2 次，$f = 2$。二分 upperBound([1,2,3,4], 2)：mid = 2，arr[2] = 3 > 2，right = 2；left = 0, right = 2 → mid = 1，arr[1] = 2 <= 2，left = 2；退出，idx = 2，答案 4 - 2 = 2（"aaa" 与 "aaaa"）。

最终返回 [1, 2]。

再看两个极端：若查询的 $f$ 大于所有词，例如 q = 10，二分会一路把 left 推到 4，idx = 4，答案 0；若 q = 0（实际不会出现，因为字符串非空），idx = 0，答案 4。两端都由 right = n 的开区间设定自然兜住，不需要特判。

再看 minCharFreq("dcce") 的走查：d < z → min = 'd'、count = 1；c < d → 重置 min = 'c'、count = 1；第二个 c 相等 → count = 2；e > c 忽略。返回 2。若遇到更小字符时忘记把 count 重置为 1 而是继续累加，这里会返回 3，全盘皆错。

代码实现

import java.util.Arrays;

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] freqWords = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            freqWords[i] = minCharFreq(words[i]);
        }
        Arrays.sort(freqWords);

        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int q = minCharFreq(queries[i]);
            // 第一个严格大于 q 的位置，其后全部满足条件。
            int idx = upperBound(freqWords, q);
            res[i] = freqWords.length - idx;
        }
        return res;
    }

    // 一次遍历同时维护最小字母与它的出现次数。
    private int minCharFreq(String s) {
        char min = 'z';
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c < min) {
                // 出现更小的字母，之前的统计作废，计数重置为 1。
                min = c;
                count = 1;
            } else if (c == min) {
                count++;
            }
        }
        return count;
    }

    private int upperBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

import "sort"

func numSmallerByFrequency(queries []string, words []string) []int {
	freqWords := make([]int, len(words))
	for i, w := range words {
		freqWords[i] = minCharFreq(w)
	}
	sort.Ints(freqWords)

	res := make([]int, len(queries))
	for i, q := range queries {
		fq := minCharFreq(q)
		// 第一个严格大于 fq 的位置，其后全部满足条件。
		idx := sort.Search(len(freqWords), func(i int) bool {
			return freqWords[i] > fq
		})
		res[i] = len(freqWords) - idx
	}
	return res
}

// 一次遍历同时维护最小字母与它的出现次数。
func minCharFreq(s string) int {
	min := byte('z')
	count := 0
	for i := 0; i < len(s); i++ {
		c := s[i]
		if c < min {
			// 出现更小的字母，之前的统计作废，计数重置为 1。
			min = c
			count = 1
		} else if c == min {
			count++
		}
	}
	return count
}

复杂度分析

时间复杂度：$O(L + n \log n + m \log n)$，其中 $n$ 为 words 数量、$m$ 为 queries 数量、$L$ 为所有字符串的总长度。计算全部 $f$ 值是 $O(L)$，排序是 $O(n \log n)$，每个查询二分一次是 $O(\log n)$；相较于预先求频次后仍逐对比较的 $O(L + mn)$，消除了 $mn$ 项。

空间复杂度：$O(n)$，freqWords 数组与 words 等长；返回数组 $O(m)$ 通常不计入。minCharFreq 内部只用两个标量。

关键点总结

先做降维：把每个字符串压成一个整数后，字符串本身就无关紧要了，问题变成纯粹的数值计数——识别出这一步，题目难度立刻下降一个档次。

「对多个查询各求一次『大于某值的个数』」的标准配方是预处理 + 排序 + 二分，把每次查询的 $O(n)$ 降到 $O(\log n)$。

严格大于用 upperBound（第一个 > target），大于等于用 lowerBound（第一个 >= target）；本题要的是前者，用错会把 $f$ 相等的词多算进去。

二分的区间语义要自洽：right = n 的左闭右开写法配合 left < right、right = mid，能让「全都不满足」自然返回 n，省掉特判。

求「最小字母的频次」用一次遍历 + 遇到更小值时重置计数，比两趟扫描或开桶都短；min 初值取 'z' 保证第一个字符必被正确处理。

排序会打乱与原数组的对应关系——只有当答案只需要「个数」而不需要「是哪些」时才能这么做，这个前提要在心里确认过。

易错点总结

错误写法：把 $f(s)$ 理解成「出现次数最少的那个字母的次数」。用例 s = "aaab"：正确的是最小字母 a 出现 3 次，$f = 3$；按错误理解会取出现最少的 b，得到 1，后续所有比较全错。

错误写法：minCharFreq 中遇到更小字符时只更新 min 而不把 count 重置为 1。用例 s = "dcce"：返回 3（把 d 的那次也算上了），正确答案是 2。

错误写法：用 lowerBound（第一个 >= q 的位置）代替 upperBound。用例 queries = ["bbb"]、words = ["a","aa","aaa","aaaa"]：$f(q) = 3$，lowerBound 返回 2，答案算成 2，而正确答案是 1——$f$ 同为 3 的 "aaa" 不该计入。

错误写法：把半开区间模板的 right = n 单独改成 n - 1，却仍使用 left < right。用例 q = 10、freqWords = [1,2,3,4]：循环最多返回 3，答案变成 1；完整的闭区间模板可以写对，但不能与半开区间更新规则混用。

错误写法：arr[mid] <= target 写成 arr[mid] < target。用例 q = 2、freqWords = [1,2,3,4]：idx 变成 1，答案算成 3，而正确答案是 2——等于目标的元素被错误地算作「大于」。

错误写法：半开区间模板中把 right = mid 写成 right = mid - 1。用例 freqWords = [1,2,3,4]、q = 2：下标 2 本是答案，却会被直接跳过并错误返回 1，计数从 2 变成 3。

错误写法：忘记对 freqWords 排序就二分。用例 words = ["aaaa","a","aa"]：freqWords = [4,1,2] 无序，二分结果毫无意义，返回值随数据乱跳。

错误写法：对每个查询都重新计算所有 words 的 $f$ 值。用例 m = n = 2000、每个词长 10：$4 \times 10^7$ 次字符操作，虽然可能勉强通过，但完全违背「重复计算应当预处理」的基本原则，面试中会被直接指出。

错误写法：min 初值取 'a'。用例 s = "bbb"：b 既不小于也不等于 'a'，count 始终为 0，返回 0 而不是 3。

错误写法：mid 写成 (left + right) / 2 并在超大数组上使用。本题规模安全，但作为习惯应写 left + (right - left) / 2，避免下标相加溢出。

错误写法：排序后仍试图用 freqWords 的下标去索引原 words。排序打乱了对应关系，任何依赖「第 idx 个词是谁」的逻辑都会取到错误的字符串。

相似题目

题目	难度	考察点
2300. 咒语和药水的成功对数	中等	结构几乎相同——排序一侧后对另一侧逐个二分计数，但判定条件是乘积门槛
34. 在排序数组中查找元素的第一个和最后一个位置	中等	`lowerBound` 与 `upperBound` 各用一次，是二者区别的最佳练习
35. 搜索插入位置	简单	左闭右开二分的最小模板，帮助固化区间语义与返回值含义
704. 二分查找	简单	标准二分模板，边界写法的起点
315. 计算右侧小于当前元素的个数	困难	同为「统计大于/小于某值的个数」，但要求动态维护，需树状数组或归并
327. 区间和的个数	困难	把区间和降维成前缀和后做范围计数，与本题的降维思路一脉相承