Hard

题目描述

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

同时给你一个二维整数数组 queries，其中 queries[i] = [li, ri]。

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

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

返回一个整数数组 answer，其中 answer[i] 是 s[li..ri] 中满足 k-约束的子字符串数量。

示例 1：

输入：s = "0001111", k = 2, queries = [[0,6]]
输出：[26]
解释：对于查询 [0, 6]，s[0..6] = "0001111" 的所有子字符串都满足 k-约束，除了 s[0..5] = "000111" 和 s[0..6] = "0001111"。

示例 2：

输入：s = "010101", k = 1, queries = [[0,5],[1,4],[2,3]]
输出：[15,9,3]
解释：长度超过 3 的 s 的子字符串不满足 k-约束。

约束条件：

  • 1 <= s.length <= 10^5
  • s[i] 是 ‘0’ 或 ‘1’
  • 1 <= k <= s.length
  • 1 <= queries.length <= 10^5
  • queries[i] == [li, ri]
  • 0 <= li <= ri < s.length
  • 所有查询都是不同的

解题思路

这是一道涉及滑动窗口和前缀和的高难度问题。

核心思路：

  1. 预计算左边界：对于每个位置 i，找到最左边的位置 left[i]，使得从 left[i] 到 i 的子字符串满足 k-约束。
  2. 前缀和优化：预计算从每个位置开始的满足 k-约束的子字符串数量的前缀和。
  3. 分段计算：对于查询 [l, r]，将答案分为两部分：
    • 右端点在某个分界点之前的子字符串，可以直接用前缀和计算
    • 右端点在分界点之后的子字符串，需要特殊处理

算法步骤：

  1. 使用滑动窗口计算每个位置的左边界 left[i]
  2. 计算前缀和数组，存储从每个位置开始的满足条件的子字符串数量
  3. 对于每个查询，找到分界点，分段计算结果

时间复杂度优化： 通过预计算避免了对每个查询都进行 O(n²) 的暴力计算，将总复杂度降低到可接受的范围。

代码实现

class Solution {
public:
    vector<long long> countKConstraintSubstrings(string s, int k, vector<vector<int>>& queries) {
        int n = s.length();
        vector<int> left(n);
        vector<long long> prefix(n + 1, 0);
        
        // 计算每个位置的左边界
        int l = 0;
        int count0 = 0, count1 = 0;
        for (int r = 0; r < n; r++) {
            if (s[r] == '0') count0++;
            else count1++;
            
            while (count0 > k && count1 > k) {
                if (s[l] == '0') count0--;
                else count1--;
                l++;
            }
            left[r] = l;
        }
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + (i - left[i] + 1);
        }
        
        vector<long long> result;
        for (auto& query : queries) {
            int l = query[0], r = query[1];
            
            // 找到分界点
            int pos = lower_bound(left.begin() + l, left.begin() + r + 1, l) - left.begin();
            
            long long ans = prefix[pos] - prefix[l];
            
            // 计算右半部分
            for (int i = pos; i <= r; i++) {
                ans += (i - max(left[i], l) + 1);
            }
            
            result.push_back(ans);
        }
        
        return result;
    }
};

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int, queries: List[List[int]]) -> List[int]:
        n = len(s)
        left = [0] * n
        prefix = [0] * (n + 1)
        
        # 计算每个位置的左边界
        l = 0
        count0 = count1 = 0
        for r in range(n):
            if s[r] == '0':
                count0 += 1
            else:
                count1 += 1
            
            while count0 > k and count1 > k:
                if s[l] == '0':
                    count0 -= 1
                else:
                    count1 -= 1
                l += 1
            left[r] = l
        
        # 计算前缀和
        for i in range(n):
            prefix[i + 1] = prefix[i] + (i - left[i] + 1)
        
        result = []
        for l, r in queries:
            # 找到分界点
            pos = l
            while pos <= r and left[pos] < l:
                pos += 1
            
            ans = prefix[pos] - prefix[l]
            
            # 计算右半部分
            for i in range(pos, r + 1):
                ans += i - max(left[i], l) + 1
            
            result.append(ans)
        
        return result

public class Solution {
    public long[] CountKConstraintSubstrings(string s, int k, int[][] queries) {
        int n = s.Length;
        int[] left = new int[n];
        long[] prefix = new long[n + 1];
        
        // 计算每个位置的左边界
        int l = 0;
        int count0 = 0, count1 = 0;
        for (int r = 0; r < n; r++) {
            if (s[r] == '0') count0++;
            else count1++;
            
            while (count0 > k && count1 > k) {
                if (s[l] == '0') count0--;
                else count1--;
                l++;
            }
            left[r] = l;
        }
        
        // 计算前缀和
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + (i - left[i] + 1);
        }
        
        long[] result = new long[queries.Length];
        for (int q = 0; q < queries.Length; q++) {
            int queryL = queries[q][0], queryR = queries[q][1];
            
            // 找到分界点
            int pos = queryL;
            while (pos <= queryR && left[pos] < queryL) {
                pos++;
            }
            
            long ans = prefix[pos] - prefix[queryL];
            
            // 计算右半部分
            for (int i = pos; i <= queryR; i++) {
                ans += i - Math.Max(left[i], queryL) + 1;
            }
            
            result[q] = ans;
        }
        
        return result;
    }
}

var countKConstraintSubstrings = function(s, k, queries) {
    const n = s.length;
    const left = new Array(n);
    const prefix = new Array(n + 1).fill(0);
    
    // 计算每个位置的左边界
    let l = 0;
    let count0 = 0, count1 = 0;
    for (let r = 0; r < n; r++) {
        if (s[r]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n + q×n)
空间复杂度O(n)

其中 n 是字符串长度，q 是查询数量。预处理阶段为 O(n)，每个查询在最坏情况下需要 O(n) 时间。