Leetcode395.至少有 K 个重复字符的最长子串

题目

395. 至少有 K 个重复字符的最长子串

算法标签: 滑动窗口

思路

首先看题目要求, 要求子串中每一个字符出现的次数都不小于$k$, 因此可以将答案视作一个集合, 可以按照子串拥有的字符类型数量进行分类, 分而治之

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>using namespace std;class Solution {
public:int longestSubstring(string s, int k) {int n = s.size();int ans = 0;for (int i = 1; i <= 26; ++i) {int l = 0, r = 0;int cnt[26] = {0};//tmp代表窗口中字符出现次数大于等于k的字符数量int type_cnt = 0, tmp = 0;while (r < n) {if (type_cnt <= i) {int u = s[r] - 'a';if (cnt[u] == 0) type_cnt++;cnt[u]++;if (cnt[u] == k) tmp++;r++;}else {int u = s[l] - 'a';if (cnt[u] == k) tmp--;cnt[u]--;if (cnt[u] == 0) type_cnt--;l++;}if (type_cnt == i && tmp == i) ans = max(ans, r - l);}}return ans;}
};