2025-03-27：统计满足 K 约束的子字符串数量Ⅰ。用go语言，给定一个二进制字符串 s 和一个整数 k，定义满足 k 约束的条件为：

字符串中 0 的数量不超过 k；

字符串中 1 的数量不超过 k。

求 s 中满足 k 约束的子字符串数量。

1 <= s.length <= 50。

1 <= k <= s.length。

s[i] 是 ‘0’ 或 ‘1’。

输入：s = “1010101”, k = 2。

输出：25。

解释：

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

题目来自leetcode3258。

大体步骤如下：

1. 初始化变量：

   • 字符串 s = “1010101”，整数 k = 2。

   • 定义一个长度为 2 的数组 count，用于统计字符 ‘0’ 和 ‘1’ 的数量。

   • 定义结果变量 res 用于存储满足 k 约束的子字符串数量。

   • 定义指针 i 和 j 用于标记子字符串的起始位置和结束位置。

2. 循环遍历字符串 s：

   • 对于每个字符 s[j]，根据其值更新 count 数组中对应的计数值。

   • 判断当前子字符串是否满足 k 约束。如果超出约束，则移动起始指针 i 直到满足约束。

   • 计算当前子字符串满足约束的数量并累加到 res 中。

3. 返回最终结果 res。

总的时间复杂度：

• 假设字符串 s 的长度为 n，算法的时间复杂度为 O(n)。因为只需遍历一次字符串 s。

总的额外空间复杂度：

• 算法的额外空间复杂度为 O(1)。因为只使用了常数个额外变量和常数个长度为 2 的数组。

这样的实现可以高效地计算满趛 k 约束的子字符串数量。

Go完整代码如下：

package main

import (
	"fmt"
)

func countKConstraintSubstrings(s string, k int) int {
	n := len(s)
	count := [2]int{}
	res := 0
	i := 0
	for j := 0; j < n; j++ {
		count[int(s[j]-'0')]++
		for count[0] > k && count[1] > k {
			count[int(s[i]-'0')]--
			i++
		}
		res += j - i + 1
	}
	return res
}

func main() {
	s := "1010101"
	k := 2
	result := countKConstraintSubstrings(s, k)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def count_k_constraint_substrings(s, k):
    n = len(s)
    count = [0, 0]
    res = 0
    i = 0

    for j in range(n):
        count[int(s[j])] += 1

        while count[0] > k and count[1] > k:
            count[int(s[i])] -= 1
            i += 1

        res += j - i + 1

    return res

s = "1010101"
k = 2
result = count_k_constraint_substrings(s, k)
print(result)