leetcode 3258.统计满足k约束的子字符串

思路一：首先直接三重循环暴力，用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++;
                    else
                    cnt0++;
                }
                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;
    }
}

原文地址：https://blog.csdn.net/m0_73917165/article/details/143705183

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！