3258.统计满足 K 约束的子字符串数量 I

【LetMeFly】3258.统计满足 K 约束的子字符串数量 I：滑动窗口（硬卷O(n)）

力扣题目链接：https://leetcode.cn/problems/count-substrings-that-satisfy-k-constraint-i/

给你一个 二进制 字符串 s 和一个整数 k。

如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

• 字符串中 0 的数量最多为 k。
• 字符串中 1 的数量最多为 k。

返回一个整数，表示 s 的所有满足 k 约束 的子字符串的数量。

 

示例 1：

输入：s = "10101", k = 1

输出：12

解释：

s 的所有子字符串中，除了 "1010"、"10101" 和 "0101" 外，其余子字符串都满足 k 约束。

示例 2：

输入：s = "1010101", k = 2

输出：25

解释：

s 的所有子字符串中，除了长度大于 5 的子字符串外，其余子字符串都满足 k 约束。

示例 3：

输入：s = "11111", k = 1

输出：15

解释：

s 的所有子字符串都满足 k 约束。

 

提示：

• 1 <= s.length <= 50
• 1 <= k <= s.length
• s[i] 是 '0' 或 '1'。

解题方法：滑动窗口

使用两个遍历cnt[0]和cnt[1]分别记录当前“窗口”中0和1的数量，使用两个指针l和r分别代表窗口的始末下标。

每次窗口右指针r向右移动一位，如果这个移动导致窗口中cnt[0] > k且cnt[1] > k，则不断右移左指针l直至窗口中子字符串符合“K约束”要求。

对于一个窗口，我们累加以r结尾的子字符串数量：$r - l + 1$。

• 时间复杂度$O(len(s))$
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int cnt[2] = {0};
        int ans = 0;
        for (int l = 0, r = 0; r < s.size(); r++) {
            cnt[s[r] - '0']++;
            while (cnt[0] > k && cnt[1] > k) {  // 啊这，De了半天原来是“任一”
                cnt[s[l++] - '0']--;
            }
            ans += r - l + 1;
        }
        return ans;
    }
};

Python

from typing import List

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        cnt = [0, 0]
        ans = 0
        l = 0
        for r in range(len(s)):
            cnt[ord(s[r]) - ord('0')] += 1
            while cnt[0] > k and cnt[1] > k:
                cnt[ord(s[l]) - ord('0')] -= 1
                l += 1
            ans += r - l + 1
        return ans

Java

class Solution {
    public int countKConstraintSubstrings(String s, int k) {
        int[] cnt = new int[2];
        int ans = 0;
        for (int l = 0, r = 0; r < s.length(); r++) {
            cnt[s.charAt(r) - '0']++;
            while (cnt[0] > k && cnt[1] > k) {
                cnt[s.charAt(l++) - '0']--;
            }
            ans += r - l + 1;
        }
        return ans;
    }
}

Go

package main

func countKConstraintSubstrings(s string, k int) (ans int) {
    cnt := make([]int, 2)
    for l, r := 0, 0; r < len(s); r++ {
        cnt[s[r] - '0']++
        for cnt[0] > k && cnt[1] > k {
            cnt[s[l] - '0']--
            l++
        }
        ans += r - l + 1
    }
    return
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/143726399