2023.6.10 比较字符串最小字母出现频次

首先按照题意把f(str)这个函数实现出来。可以考虑用哈希表+sort来实现。
然后根据题目的数据范围，一个字符串最长为2000，可以知道，\(f(str) \in [1, 2000]\)。
所以可以考虑用前缀和来处理，定义一个长度为2001的数组s，用来作为前缀和数组，\(s[i]\)表示f值小于等于i的字符串个数。
每一次query的答案即为\(s[2000] - s[f(query) + 1]\)。即所有f值大于f(query)的字符串个数。

use std::collections::{BTreeSet, HashMap};

impl Solution 
{
    pub fn num_smaller_by_frequency(queries: Vec<String>, words: Vec<String>) -> Vec<i32> 
    {
        fn f(s: &str) -> i32
        {
            let mut chars: Vec<char> = Vec::new();
            let mut map: HashMap<char, i32> = HashMap::new();
            for c in s.chars()
            {
                chars.push(c);
                map.entry(c).and_modify(|v| *v += 1).or_insert(1);
            }

            chars.sort();
            map[&chars[0]]
        }

        let mut s = vec![0; 2001];
        for word in words { s[f(&word) as usize] += 1; }
        for i in 1..2001_usize { s[i] += s[i - 1]; }

        let mut res: Vec<i32> = Vec::new();
        for query in queries
        {
            let x = f(&query) as usize;
            res.push(s[2000] - s[x]);
        }

        res
    }
}