列表

详情


100404. 统计满足 K 约束的子字符串数量 II

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

另给你一个二维整数数组 queries ,其中 queries[i] = [li, ri]

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

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

 

示例 1:

输入:s = "0001111", k = 2, queries = [[0,6]]

输出:[26]

解释:

对于查询 [0, 6]s[0..6] = "0001111" 的所有子字符串中,除 s[0..5] = "000111"s[0..6] = "0001111" 外,其余子字符串都满足 k 约束。

示例 2:

输入:s = "010101", k = 1, queries = [[0,5],[1,4],[2,3]]

输出:[15,9,3]

解释:

s 的所有子字符串中,长度大于 3 的子字符串都不满足 k 约束。

 

提示:

原站题解

去查看

上次编辑到这里,代码来自缓存 点击恢复默认模板
class Solution { public: vector<long long> countKConstraintSubstrings(string s, int k, vector<vector<int>>& queries) { } };

javascript 解法, 执行用时: 61 ms, 内存消耗: 88.3 MB, 提交时间: 2024-11-13 00:11:29

/**
 * @param {string} s
 * @param {number} k
 * @param {number[][]} queries
 * @return {number[]}
 */
var countKConstraintSubstrings = function(s, k, queries) {
    const n = s.length;
    const count = [0, 0];
    const right = Array(n).fill(n);
    const prefix = Array(n + 1).fill(0);
    let i = 0;
    for (let j = 0; j < n; ++j) {
        count[s[j] - '0']++;
        while (count[0] > k && count[1] > k) {
            count[s[i] - '0']--;
            right[i] = j;
            i++;
        }
        prefix[j + 1] = prefix[j] + j - i + 1;
    }

    const res = [];
    for (const query of queries) {
        const l = query[0], r = query[1];
        const i = Math.min(right[l], r + 1);
        const part1 = Math.floor((i - l + 1) * (i - l) / 2);
        const part2 = prefix[r + 1] - prefix[i];
        res.push(part1 + part2);
    }
    return res;
};

rust 解法, 执行用时: 16 ms, 内存消耗: 10.5 MB, 提交时间: 2024-11-13 00:11:11

impl Solution {
    pub fn count_k_constraint_substrings(s: String, k: i32, queries: Vec<Vec<i32>>) -> Vec<i64> {
        let n = s.len();
        let s: Vec<u8> = s.bytes().collect(); // Convert to bytes for faster access
        let mut count = [0, 0];
        let mut right: Vec<usize> = vec![n; n];
        let mut prefix: Vec<i64> = vec![0; n + 1];
        let mut i = 0;

        for j in 0..n {
            count[s[j] as usize - b'0' as usize] += 1; // Direct byte access
            while count[0] > k && count[1] > k {
                count[s[i] as usize - b'0' as usize] -= 1;
                right[i] = j;
                i += 1;
            }
            prefix[j + 1] = prefix[j] + (j - i + 1) as i64;
        }

        let mut res: Vec<i64> = Vec::with_capacity(queries.len()); // Pre-allocate for efficiency
        for query in queries {
            let l = query[0] as usize;
            let r = query[1] as usize;
            let i = std::cmp::min(right[l], r + 1);
            let part1 = (i - l + 1) * (i - l) / 2;
            let part2 = prefix[r + 1] - prefix[i];
            res.push(part1 as i64 + part2);
        }
        res
    }
}

python3 解法, 执行用时: 218 ms, 内存消耗: 59.7 MB, 提交时间: 2024-10-21 22:19:23

class Solution:
    def countKConstraintSubstrings(self, s: str, k: int, queries: List[List[int]]) -> List[int]:
        n = len(s)
        right = [n] * n
        pre = [0] * (n + 1)
        cnt = [0, 0]
        l = 0
        for i, c in enumerate(s):
            cnt[ord(c) & 1] += 1
            while cnt[0] > k and cnt[1] > k:
                cnt[ord(s[l]) & 1] -= 1
                right[l] = i
                l += 1
            pre[i + 1] = pre[i] + i - l + 1

        ans = []
        for l, r in queries:
            j = min(right[l], r + 1)
            ans.append(pre[r + 1] - pre[j] + (j - l + 1) * (j - l) // 2)
        return ans


    def countKConstraintSubstrings2(self, s: str, k: int, queries: List[List[int]]) -> List[int]:
        n = len(s)
        left = [0] * n
        pre = [0] * (n + 1)
        cnt = [0, 0]
        l = 0
        for i, c in enumerate(s):
            cnt[ord(c) & 1] += 1
            while cnt[0] > k and cnt[1] > k:
                cnt[ord(s[l]) & 1] -= 1
                l += 1
            left[i] = l
            # 计算 i-left[i]+1 的前缀和
            pre[i + 1] = pre[i] + i - l + 1

        ans = []
        for l, r in queries:
            j = bisect_left(left, l, l, r + 1)
            ans.append(pre[r + 1] - pre[j] + (j - l + 1) * (j - l) // 2)
        return ans

golang 解法, 执行用时: 12 ms, 内存消耗: 20 MB, 提交时间: 2024-10-21 22:18:45

func countKConstraintSubstrings1(s string, k int, queries [][]int) []int64 {
	n := len(s)
	left := make([]int, n)
	sum := make([]int, n+1)
	cnt := [2]int{}
	l := 0
	for i, c := range s {
		cnt[c&1]++
		for cnt[0] > k && cnt[1] > k {
			cnt[s[l]&1]--
			l++
		}
		left[i] = l
		// 计算 i-left[i]+1 的前缀和
		sum[i+1] = sum[i] + i - l + 1
	}

	ans := make([]int64, len(queries))
	for i, q := range queries {
		l, r := q[0], q[1]
		j := l + sort.SearchInts(left[l:r+1], l)
		ans[i] = int64(sum[r+1] - sum[j] + (j-l+1)*(j-l)/2)
	}
	return ans
}

// 方法二:预处理
func countKConstraintSubstrings(s string, k int, queries [][]int) []int64 {
	n := len(s)
	right := make([]int, n)
	sum := make([]int, n+1)
	cnt := [2]int{}
	l := 0
	for i, c := range s {
		cnt[c&1]++
		for cnt[0] > k && cnt[1] > k {
			cnt[s[l]&1]--
			right[l] = i
			l++
		}
		sum[i+1] = sum[i] + i - l + 1
	}
	// 剩余没填的 right[l] 均为 n
	for ; l < n; l++ {
		right[l] = n
	}

	ans := make([]int64, len(queries))
	for i, q := range queries {
		l, r := q[0], q[1]
		j := min(right[l], r+1)
		ans[i] = int64(sum[r+1] - sum[j] + (j-l+1)*(j-l)/2)
	}
	return ans
}

cpp 解法, 执行用时: 28 ms, 内存消耗: 140.9 MB, 提交时间: 2024-10-21 22:18:01

class Solution {
public:
    vector<long long> countKConstraintSubstrings(string s, int k, vector<vector<int>>& queries) {
        int n = s.length();
        vector<int> right(n, n);
        vector<long long> sum(n + 1);
        int cnt[2]{}, l = 0;
        for (int i = 0; i < n; i++) {
            cnt[s[i] & 1]++;
            while (cnt[0] > k && cnt[1] > k) {
                cnt[s[l] & 1]--;
                right[l++] = i;
            }
            sum[i + 1] = sum[i] + i - l + 1;
        }

        vector<long long> ans(queries.size());
        for (int i = 0; i < queries.size(); i++) {
            int l = queries[i][0], r = queries[i][1];
            int j = min(right[l], r + 1);
            ans[i] = sum[r + 1] - sum[j] + (long long) (j - l + 1) * (j - l) / 2;
        }
        return ans;
    }

    // 滑动窗口+前缀和+二分查找
    vector<long long> countKConstraintSubstrings2(string s, int k, vector<vector<int>>& queries) {
        int n = s.length();
        vector<int> left(n);
        vector<long long> sum(n + 1);
        int cnt[2]{}, l = 0;
        for (int i = 0; i < n; i++) {
            cnt[s[i] & 1]++;
            while (cnt[0] > k && cnt[1] > k) {
                cnt[s[l++] & 1]--;
            }
            left[i] = l;
            // 计算 i-left[i]+1 的前缀和
            sum[i + 1] = sum[i] + i - l + 1;
        }

        vector<long long> ans(queries.size());
        for (int i = 0; i < queries.size(); i++) {
            int l = queries[i][0], r = queries[i][1];
            int j = lower_bound(left.begin() + l, left.begin() + r + 1, l) - left.begin();
            ans[i] = sum[r + 1] - sum[j] + (long long) (j - l + 1) * (j - l) / 2;
        }
        return ans;
    }
};

java 解法, 执行用时: 35 ms, 内存消耗: 103.3 MB, 提交时间: 2024-10-21 22:17:16

class Solution {
    public long[] countKConstraintSubstrings(String S, int k, int[][] queries) {
        char[] s = S.toCharArray();
        int n = s.length;
        int[] left = new int[n];
        long[] sum = new long[n + 1];
        int[] cnt = new int[2];
        int l = 0;
        for (int i = 0; i < n; i++) {
            cnt[s[i] & 1]++;
            while (cnt[0] > k && cnt[1] > k) {
                cnt[s[l++] & 1]--;
            }
            left[i] = l;
            // 计算 i-left[i]+1 的前缀和
            sum[i + 1] = sum[i] + i - l + 1;
        }

        long[] ans = new long[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int ql = queries[i][0];
            int qr = queries[i][1];
            int j = lowerBound(left, ql - 1, qr + 1, ql);
            ans[i] = sum[qr + 1] - sum[j] + (long) (j - ql + 1) * (j - ql) / 2;
        }
        return ans;
    }

    // 返回在开区间 (left, right) 中的最小的 j,满足 nums[j] >= target
    // 如果没有这样的数,返回 right
    // 原理见 https://www.bilibili.com/video/BV1AP41137w7/
    private int lowerBound(int[] nums, int left, int right, int target) {
        while (left + 1 < right) { // 区间不为空
            // 循环不变量:
            // nums[left] < target
            // nums[right] >= target
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid; // 范围缩小到 (mid, right)
            } else {
                right = mid; // 范围缩小到 (left, mid)
            }
        }
        return right;
    }

    // 方法二:预处理
    public long[] countKConstraintSubstrings2(String S, int k, int[][] queries) {
        char[] s = S.toCharArray();
        int n = s.length;
        int[] right = new int[n];
        long[] sum = new long[n + 1];
        int[] cnt = new int[2];
        int l = 0;
        for (int i = 0; i < n; i++) {
            cnt[s[i] & 1]++;
            while (cnt[0] > k && cnt[1] > k) {
                cnt[s[l] & 1]--;
                right[l++] = i;
            }
            sum[i + 1] = sum[i] + i - l + 1;
        }
        // 剩余没填的 right[l] 均为 n
        Arrays.fill(right, l, n, n);

        long[] ans = new long[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int ql = queries[i][0];
            int qr = queries[i][1];
            int j = Math.min(right[ql], qr + 1);
            ans[i] = sum[qr + 1] - sum[j] + (long) (j - ql + 1) * (j - ql) / 2;
        }
        return ans;
    }
}

上一题