count-substrings-that-satisfy-k-constraint-i

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>.

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 denoting the number of substrings of <code>s</code> that satisfy the k-constraint.

&nbsp;
Example 1:

<div class="example-block">
Input: s = &quot;10101&quot;, k = 1

Output: 12

Explanation:

Every substring of <code>s</code> except the substrings <code>&quot;1010&quot;</code>, <code>&quot;10101&quot;</code>, and <code>&quot;0101&quot;</code> satisfies the k-constraint.
</div>

Example 2:

<div class="example-block">
Input: s = &quot;1010101&quot;, k = 2

Output: 25

Explanation:

Every substring of <code>s</code> except the substrings with a length greater than 5 satisfies the k-constraint.
</div>

Example 3:

<div class="example-block">
Input: s = &quot;11111&quot;, k = 1

Output: 15

Explanation:

All substrings of <code>s</code> satisfy the k-constraint.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 50 </code></li>
	<li><code>1 &lt;= k &lt;= s.length</code></li>
	<li><code>s[i]</code> is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

countKConstraintSubstrings

Count Substrings That Satisfy K-Constraint I

String

Sliding Window

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

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

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

返回一个整数，表示 <code>s</code> 的所有满足 k 约束 的子字符串的数量。

&nbsp;

示例 1：

<div class="example-block">
输入：s = "10101", k = 1

输出：12

解释：

<code>s</code> 的所有子字符串中，除了 <code>"1010"</code>、<code>"10101"</code> 和 <code>"0101"</code> 外，其余子字符串都满足 k 约束。
</div>

示例 2：

<div class="example-block">
输入：s = "1010101", k = 2

输出：25

解释：

<code>s</code> 的所有子字符串中，除了长度大于 5 的子字符串外，其余子字符串都满足 k 约束。
</div>

示例 3：

<div class="example-block">
输入：s = "11111", k = 1

输出：15

解释：

<code>s</code> 的所有子字符串都满足 k 约束。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length &lt;= 50</code></li>
	<li><code>1 &lt;= k &lt;= s.length</code></li>
	<li><code>s[i]</code> 是 <code>'0'</code> 或 <code>'1'</code>。</li>
</ul>