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

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

• 枚举子串中的字符种数

  • 1~26枚举 同时每一次都遍历整个字符串

• 用哈希表记录每个字母出现次数

•   class Solution {
    public:
        int longestSubstring(string s, int k) {
            int n = s.size(),res = 0;
            unordered_map<char,int> cnt;
            for(int t=1;t<=26;t++)
            {
                int tol=0;  //字母种数
                cnt.clear();
                for(int r=0,l=0;r<n;r++)
                {
                    //第一次遍历到 tol++
                    if(!cnt.count(s[r])) tol++;
                    cnt[s[r]] ++;
                    while(tol > t)  //种数超了 left++
                    {
                        if(--cnt[s[l]] == 0)
                        {
                            cnt.erase(s[l]);
                            tol --;  //种类-1
                        }
                        l ++;
                    }
                    bool flag=true;
                    for(auto c:cnt)  //遍历所有出现过的字母
                    {
                        if(c.second < k) flag = false;
                    }
                    if(flag) res = max(res,r-l+1);
                }
            }
            return res;
        }
    };