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;}
}