一件代发货源网1688_机械行业网站建设制作开发方案_百度一下你就知道百度官网_百度推广开户费用多少

【LeetCode】1297、子串的最大出现次数

一、定长滑动窗口

1.1 定长滑动窗口

参考
本题, 只需要 考虑 minSize, 而不需要考虑 maxSize
以例1为例: s = “aababcaab”, maxLetters = 2, minSize = 3, maxSize = 4
结论: 若 “[minSize, maxSize] 之间的” 的 aaba 满足要求, 则 “minSize的” aab 一定满足要求

原因:

1. 因为首先 aab 满足 条件2, 即长度在 [minSize, maxSize] 之间
2. 若 aaba 都满足 条件1了, 即不同字母出现的次数<=maxLetters, 则长度更短的 aab 更满足要求了(因为字母都变少了, 肯定不同字母出现的次数更<=maxLetters了)

注意题意不是很清楚时需结合示例理解, 以例一为例, 答案为2(aab, aab), 而不是5(aab, aba, bab, caa, aab)
即答案要求的是"相同子串"的个数

二、多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp
// 定长滑动窗口, 窗口长度为k, 窗口内元素种类小于等于maxLetters
class Solution {
public:int maxFreq(string s, int maxLetters, int minSize, int maxSize) {int k = minSize; // window sizeunordered_map<char, int> window; // char in window to cntunordered_map<string, int> ans; // substring to cntfor (int i = 0; i < s.size(); i++) {// 入window[s[i]]++;if (i < k - 1) continue;// 更新if (window.size() <= maxLetters) {string ss = s.substr(i-k+1, k);ans[ss]++;}// 出char out = s[i-k+1];window[out]--;if (window[out] == 0) window.erase(out);}int mx = 0;for (auto kv:ans) {mx = max(mx, kv.second);}return mx;}
};

// go 同上

# python
class Solution:def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:# 定长滑动窗口# 1. 不同字母出现次数<=maxLetters, 需用哈希表# 2. 窗口长度为 minSize# 求满足条件的窗口的次数k = minSize  # 根据题意分析, 只需要处理窗口定长为minSize时即可ans = Counter()  # 结果的哈希表, k是子串字符串, v是该子串字符串出现了几次window = (Counter())  # 窗口哈希表, k是定长窗口内的元素(满足窗口长度时, 它也就是子串字符串), v是窗口内各字符出现的次数for i, x in enumerate(s):# 入window[x] += 1# 更新if i < minSize - 1:continueif len(window) <= maxLetters:ss = s[i - k + 1: i + 1]ans[ss] += 1  # 把子串加入结果哈希表中# 出out = s[i - k + 1]window[out] -= 1if window[out] == 0:del window[out]return max(ans.values()) if ans else 0

// rust
use std::collections::HashMap;
impl Solution {pub fn max_freq(s: String, max_letters: i32, min_size: i32, max_size: i32) -> i32 {let mut window = HashMap::new();let mut ans: HashMap<String, i32>  = HashMap::new();let k = min_size as usize;let s_chars: Vec<char> = s.chars().collect();for i in 0..s.len() {*window.entry(s_chars[i]).or_insert(0) += 1;if i < k-1 {continue;}if window.len() <= max_letters as usize {let ss = s_chars[i-k+1..=i].iter().collect();*ans.entry(ss).or_insert(0) += 1;}let out = s_chars[i-k+1];if let Some(count) = window.get_mut(&out) {*count -= 1;if *count == 0 {window.remove(&out);}}}let mut mx = 0;for &count in ans.values() {mx = mx.max(count);}mx}
}

// js
/*** @param {string} s* @param {number} maxLetters* @param {number} minSize* @param {number} maxSize* @return {number}*/
var maxFreq = function(s, maxLetters, minSize, maxSize) {const k = minSize;const window = new Map();const ans = new Map();for (let i = 0; i < s.length; i++) {const charin = s[i];window.set(charin, (window.get(charin) || 0) + 1);if (i < k-1) continue;if (window.size <= maxLetters) {const ss = s.substring(i-k+1, i+1);ans.set(ss, (ans.get(ss) || 0) + 1);}const out = s[i-k+1];window.set(out, window.get(out) - 1);if (window.get(out) === 0) window.delete(out);}let mx = 0;for (const [_, count] of ans) {mx = Math.max(mx, count);}return mx;
};

// ts 同 js