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

约 6 分钟
文章信息 6 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 字符串 哈希表 排序 二分查找

题目描述

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

image-20260929075256403

image-20260929075256483

题意分析

对非空字符串定义 f(s)：先找到其中字典序最小的字母，再数出这个字母出现多少次。它不是所有字母频次里的最小值，也不由字符串总长度直接决定。

对每个查询字符串，统计 words 中有多少个单词的 f 值严格大于当前查询的 f 值，按查询原顺序返回数量。相等频次不能计入，同频的不同单词仍分别贡献一个。

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

核心思路

[!blue]

每个单词参与比较时只需要一个整数 f，原字符顺序不再重要。先为所有 words 计算频次值并排序，就能把每次查询转成“有多少个数严格大于某个阈值”，无需每个查询都重新扫描所有单词。

计算 f 时，同时维护当前最小字母和它的次数。读到更小字母，之前次数属于旧字母，应立即把最小字母改为新字母、次数重置为一；读到相同字母则加一，更大的字母不影响结果。输入只含小写字母，初始设最小字母为 z、次数为零，可以覆盖整个字母范围。

排序后，小于等于查询频次 q 的值都在左侧，严格大于 q 的值构成一个连续后缀。二分找到这个后缀的第一个位置 idx：中点不大于 q 时连同左边排除，中点大于 q 时保留它作为边界并向左收缩。

最终满足条件的位置正好是 [idx, n)，数量为 n - idx。边界可以等于 n，表示没有任何单词合格；也可以为零，表示全部单词合格。只统计数量，不需要保留频次数组与原单词下标之间的对应关系。

解题步骤

  1. 为每个单词扫描字符，计算最小字母的出现频次，保存到整数数组。
  2. 将频次数组升序排序。
  3. 按原查询顺序计算当前频次，二分查找第一个严格大于它的位置。
  4. 用单词总数减去边界下标，写入当前查询答案。
  5. 返回全部查询结果。

代码实现

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 + 1) + m\log(n + 1))$，L 为所有输入字符串的字符总数，n 为单词数，m 为查询数；各字符串只计算一次频次。
  • 空间复杂度：$O(n)$ 保存单词频次数组，返回结果另占 $O(m)$。

关键点总结

[!green]

  • 先选字典序最小的字母，再统计它的次数，两个步骤不能反过来。
  • 一次预处理单词集合，之后每次只对整数频次查找严格上界。
  • 二分相等时也必须向右排除，才能符合严格大于。
  • 合格后缀从边界本身开始计数，数量为总长减边界。

易错点总结

[!yellow]

  • 出现更小字母时保留旧计数，把不同字母的次数混在一起。
  • 使用第一个大于等于查询值的位置，会多计入频次相等的单词。
  • 频次数组未经排序就二分，没有单调边界可以利用。
  • 将最小字母初始化为 a，但又只在更小时更新，没有实际 a 的字符串就可能一直得到零。
  • 对相同频次去重，会把不同单词错误合并，少算数量。

相似题目

题目 难度 关联与区别
2300. 咒语和药水的成功对数 中等 同样先把另一组排序，再对每个查询二分符合阈值的后缀数量，本题比较最小字母频次。
35. 搜索插入位置 简单 需要找第一个频次严格大于查询值的位置，不能把大于误写成大于等于。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/95771235
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！