A Letter Reaches k Repeats

Medium

You are given a string text of lowercase English letters and an integer times. Count the contiguous substrings of text in which **at least one** letter occurs times times or more. Substrings with the same content but at different positions count separately.

Example 1

text="banana", times=3 → 2

The letter a shows up three times only in anana (starting at index 1) and in the whole banana.

Example 2

text="xyz", times=1 → 6

With times = 1 every piece qualifies: 3 + 2 + 1 = 6 of them.

Example 3

text="aabb", times=2 → 5

Constraints

1 ≤ len(text) ≤ 3000
1 ≤ times ≤ len(text)
text consists of lowercase English letters only

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Sliding Window

Similar problems

Longest Repeat-Free Stretch Medium Two-Letter Stretch Medium Recurring Gene Windows Medium Window with Few Kinds of Letters Medium Every Letter at Least k Times Medium

Input

text="banana", times=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 105 tests on the server, hidden ones included.