当前位置：首页 > article >正文

Rust 力扣 - 1297. 子串的最大出现次数

article 2024/11/5 16:25:47

文章目录

题目描述
题解思路
题解代码
题目链接

题目描述

在这里插入图片描述

题解思路

越短的子串出现的次数越多，我们只需要求某个长度为min_size的子串出现的次数，并且该子串中不重复字符小于等于max_letters的数量

遍历长度长度为min_size的子串，然后将不重复字符小于等于max_letters的子串加入哈希表中计数

然后返回哈希表中满足约束条件的子串的数量最大值

题解代码

use std::collections::HashMap;

impl Solution {
    pub fn max_freq(s: String, max_letters: i32, min_size: i32, max_size: i32) -> i32 {
        let cs = s.as_bytes();
        let mut map = HashMap::new();

        let mut win = HashMap::new();

        for i in 0..min_size as usize {
            win.insert(cs[i], i);
        }

        if win.len() <= max_letters as usize {
            map.insert(&s[0..min_size as usize], 1);
        }

        for i in min_size as usize..cs.len() {
            if let Some(start) = win.get(&cs[i - min_size as usize]) {
                if start <= &(i - min_size as usize) {
                    win.remove(&cs[i - min_size as usize]);
                }
            }

            win.insert(cs[i], i);
            if win.len() <= max_letters as usize {
                if let Some(count) = map.get_mut(&s[i - min_size as usize + 1 .. i + 1]) {
                    *count += 1;
                } else {
                    map.insert(&s[i - min_size as usize + 1 .. i + 1], 1);
                }
            }
        }

        let mut ans = 0;

        for (_, v) in &map {
            ans = ans.max(*v);
        }

        return ans;
    }
}