思路一:首先直接三重循环暴力,用substring解决子字符串的截取问题。
class Solution {public int countKConstraintSubstrings(String s, int k) {if(s.length()<=0)return 0;int n=s.length();int res=0;for(int i=0;i<n;i++){for(int j=0;j<=i;j++){int cnt1=0;int cnt0=0;String buf=s.substring(j,i+1);for(int k1=0;k1<buf.length();k1++){if(buf.charAt(k1)=='1')cnt1++;elsecnt0++;}if(cnt0<=k||cnt1<=k){res++;}}}return res;}
}
思路二:滑动窗口,一般面对子字符串问题,我们应该想到双指针,前缀和,以及滑动窗口这样一系列的技巧。
滑动窗口稍微复习一下,可变滑动窗口,窗口里面的连续子字符串都是满足题意的,所以在计数子字符串数量的时候,需要额外注意一下。
还有,左指针通常是不会变的,除非窗口内的东西是不满足题意的,一般都是右指针动。然后在指针动的同时,我们一遍计数,一遍判断即可。
class Solution {public int countKConstraintSubstrings(String s, int k) {int n=s.length();if(n==1)return 1;int res=0;int l=0;int cnt[]=new int[2];for(int r=0;r<n;r++){cnt[s.charAt(r)-'0']++;while(cnt[1]>k&&cnt[0]>k){cnt[s.charAt(l++)-'0']--;}res+=r-l+1;}return res;}
}