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

【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 size
        unordered_map<char, int> window; // char in window to cnt
        unordered_map<string, int> ans; // substring to cnt
        for (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:
                continue
            if len(window) <= maxLetters:
                ss = s[i - k + 1: i + 1]
                ans[ss] += 1  # 把子串加入结果哈希表中

            # 出
            out = s[i - k + 1]
            window[out] -= 1
            if 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