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

福大大架构师每日一题

发布于 2025-03-27 16:04:01

4500

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

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-*-

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

    for j inrange(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)