目录

题目

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

算法标签: 滑动窗口

思路

首先看题目要求, 要求子串中每一个字符出现的次数都不小于 k 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;
    }
};