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

解题思路

一道滑动窗口题型，不过滑动窗口的长度是不同种类元素的个数。
这里需要定义两个变量 cnt,overk。overk表示的是满足大于k的字符数,
cnt表示的是该窗口中不同元素的个数且cnt>=1&&cnt<=26。

相关代码

class Solution {
    public int longestSubstring(String s, int k) {
        char c[] = s.toCharArray(); 
        int res=0;
        //length表示的是该小段区间 规定的不同种类元素的个数
        for(int length=1;length<=26;length++){
            int a[] = new int[26];
            //overk表示的是满足大于k的字符数
            //cnt表示的是该窗口中不同元素的个数
            int cnt=0;
            int overk=0; 
            for(int i=0,j=0;i<c.length;i++){
                a[c[i]-'a']++;
                if(a[c[i]-'a']==1) cnt++;
                if(a[c[i]-'a']==k) overk++; 
                while(j<i&&cnt>length){
                    if(a[c[j]-'a']==1) cnt--;
                    if(a[c[j]-'a']==k) overk--;
                    a[c[j]-'a']--;
                    j++;
                }
                if(overk==length) res = Math.max(res,i-j+1);
            }
        }
        return res;
    }
}