文章目录
- 题目描述
- 题解思路
- 题解代码
- 题目链接
题目描述
题解思路
越短的子串出现的次数越多，我们只需要求某个长度为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;}
}
题目链接
https://leetcode.cn/problems/maximum-number-of-occurrences-of-a-substring/
