count-substrings-with-k-frequency-characters-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

Given a string <code>s</code> and an integer <code>k</code>, return the total number of substrings of <code>s</code> where at least one character appears at least <code>k</code> times.

&nbsp;
Example 1:

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

Output: 4

Explanation:

The valid substrings are:

<ul>
	<li><code>&quot;aba&quot;</code> (character <code>&#39;a&#39;</code> appears 2 times).</li>
	<li><code>&quot;abac&quot;</code> (character <code>&#39;a&#39;</code> appears 2 times).</li>
	<li><code>&quot;abacb&quot;</code> (character <code>&#39;a&#39;</code> appears 2 times).</li>
	<li><code>&quot;bacb&quot;</code> (character <code>&#39;b&#39;</code> appears 2 times).</li>
</ul>
</div>

Example 2:

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

Output: 15

Explanation:

All substrings are valid because every character appears at least once.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= s.length &lt;= 3000</code></li>
	<li><code>1 &lt;= k &lt;= s.length</code></li>
	<li><code>s</code> consists only of lowercase English letters.</li>
</ul>

numberOfSubstrings

Count Substrings With K-Frequency Characters I

Hash Table

String

Sliding Window

给你一个字符串 <code>s</code> 和一个整数 <code>k</code>，在 <code>s</code> 的所有子字符串中，请你统计并返回 至少有一个 字符 至少出现 <code>k</code> 次的子字符串总数。

子字符串 是字符串中的一个连续、 非空 的字符序列。

&nbsp;

示例 1：

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

输出： 4

解释：

符合条件的子字符串如下：

<ul>
	<li><code>"aba"</code>（字符 <code>'a'</code> 出现 2 次）。</li>
	<li><code>"abac"</code>（字符 <code>'a'</code> 出现 2 次）。</li>
	<li><code>"abacb"</code>（字符 <code>'a'</code> 出现 2 次）。</li>
	<li><code>"bacb"</code>（字符 <code>'b'</code> 出现 2 次）。</li>
</ul>
</div>

示例 2：

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

输出： 15

解释：

所有子字符串都有效，因为每个字符至少出现一次。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= s.length &lt;= 3000</code></li>
	<li><code>1 &lt;= k &lt;= s.length</code></li>
	<li><code>s</code> 仅由小写英文字母组成。</li>
</ul>