100404. 统计满足 K 约束的子字符串数量 II
给你一个 二进制 字符串 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"
的所有子字符串中,除 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 约束。
提示:
1 <= s.length <= 105
s[i]
是 '0'
或 '1'
1 <= k <= s.length
1 <= queries.length <= 105
queries[i] == [li, ri]
0 <= li <= ri < s.length
原站题解
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; } }