count-substrings-that-satisfy-k-constraint-ii

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given a binary string <code>s</code> and an integer <code>k</code>.

You are also given a 2D integer array <code>queries</code>, where <code>queries[i] = [li, ri]</code>.

A binary string satisfies the k-constraint if either of the following conditions holds:

<ul>
	<li>The number of <code>0</code>&#39;s in the string is at most <code>k</code>.</li>
	<li>The number of <code>1</code>&#39;s in the string is at most <code>k</code>.</li>
</ul>

Return an integer array <code>answer</code>, where <code>answer[i]</code> is the number of substrings of <code>s[li..ri]</code> that satisfy the k-constraint.

&nbsp;
Example 1:

<div class="example-block">
Input: s = &quot;0001111&quot;, k = 2, queries = [[0,6]]

Output: [26]

Explanation:

For the query <code>[0, 6]</code>, all substrings of <code>s[0..6] = &quot;0001111&quot;</code> satisfy the k-constraint except for the substrings <code>s[0..5] = &quot;000111&quot;</code> and <code>s[0..6] = &quot;0001111&quot;</code>.
</div>

Example 2:

<div class="example-block">
Input: s = &quot;010101&quot;, k = 1, queries = [[0,5],[1,4],[2,3]]

Output: [15,9,3]

Explanation:

The substrings of <code>s</code> with a length greater than 3 do not satisfy the k-constraint.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 105</code></li>
	<li><code>s[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
	<li><code>1 &lt;= k &lt;= s.length</code></li>
	<li><code>1 &lt;= queries.length &lt;= 105</code></li>
	<li><code>queries[i] == [li, ri]</code></li>
	<li><code>0 &lt;= li &lt;= ri &lt; s.length</code></li>
	<li>All queries are distinct.</li>
</ul>

countKConstraintSubstrings

Count Substrings That Satisfy K-Constraint II

Array

String

Binary Search

Prefix Sum

Sliding Window

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

另给你一个二维整数数组 <code>queries</code> ，其中 <code>queries[i] = [li, ri]</code> 。

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

<ul>
	<li>字符串中 <code>0</code> 的数量最多为 <code>k</code>。</li>
	<li>字符串中 <code>1</code> 的数量最多为 <code>k</code>。</li>
</ul>

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

&nbsp;

示例 1：

<div class="example-block">
输入：s = "0001111", k = 2, queries = [[0,6]]

输出：[26]

解释：

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

示例 2：

<div class="example-block">
输入：s = "010101", k = 1, queries = [[0,5],[1,4],[2,3]]

输出：[15,9,3]

解释：

<code>s</code> 的所有子字符串中，长度大于 3 的子字符串都不满足 k 约束。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length &lt;= 105</code></li>
	<li><code>s[i]</code> 是 <code>'0'</code> 或 <code>'1'</code></li>
	<li><code>1 &lt;= k &lt;= s.length</code></li>
	<li><code>1 &lt;= queries.length &lt;= 105</code></li>
	<li><code>queries[i] == [li, ri]</code></li>
	<li><code>0 &lt;= li &lt;= ri &lt; s.length</code></li>
	<li>所有查询互不相同</li>
</ul>