Easy

题目描述

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

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

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

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

示例 1：

输入: s = "10101", k = 1
输出: 12
解释: 除了子字符串 "1010"、"10101" 和 "0101" 外，s 的每个子字符串都满足 k 约束。

示例 2：

输入: s = "1010101", k = 2
输出: 25
解释: 除了长度大于 5 的子字符串外，s 的每个子字符串都满足 k 约束。

示例 3：

输入: s = "11111", k = 1
输出: 15
解释: s 的所有子字符串都满足 k 约束。

提示：

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

解题思路

这道题要求统计满足 k 约束的子字符串数量，我们可以用两种方法来解决：

方法一：暴力枚举（推荐） 对于长度较小的字符串（n ≤ 50），直接枚举所有子字符串是最直观的方法。对于每个可能的子字符串 s[i:j]，统计其中 0 和 1 的个数，如果任一个数量不超过 k，则该子字符串满足条件。

方法二：滑动窗口 可以使用滑动窗口优化，但由于题目规模较小，优化效果不明显。对每个起始位置，用双指针扩展窗口，当窗口内 0 和 1 的数量都超过 k 时停止扩展。

考虑到代码简洁性和题目数据规模，暴力枚举是最合适的解法。时间复杂度虽然是 O(n³)，但在 n ≤ 50 的约束下完全可以接受。

代码实现

class Solution {
public:
    int countKConstraintSubstrings(string s, int k) {
        int n = s.length();
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int zeros = 0, ones = 0;
            for (int j = i; j < n; j++) {
                if (s[j] == '0') zeros++;
                else ones++;
                
                if (zeros <= k || ones <= k) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int) -> int:
        n = len(s)
        count = 0
        
        for i in range(n):
            zeros = ones = 0
            for j in range(i, n):
                if s[j] == '0':
                    zeros += 1
                else:
                    ones += 1
                
                if zeros <= k or ones <= k:
                    count += 1
        
        return count

public class Solution {
    public int CountKConstraintSubstrings(string s, int k) {
        int n = s.Length;
        int count = 0;
        
        for (int i = 0; i < n; i++) {
            int zeros = 0, ones = 0;
            for (int j = i; j < n; j++) {
                if (s[j] == '0') zeros++;
                else ones++;
                
                if (zeros <= k || ones <= k) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

var countKConstraintSubstrings = function(s, k) {
    let count = 0;
    let n = s.length;
    
    for (let i = 0; i < n; i++) {
        let zeros = 0;
        let ones = 0;
        
        for (let j = i; j < n; j++) {
            if (s[j] === '0') {
                zeros++;
            } else {
                ones++;
            }
            
            if (zeros <= k || ones <= k) {
                count++;
            } else {
                break;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n²)
空间复杂度O(1)