Every Letter the Same Number of Times

Medium

You are given a string text of lowercase English letters and an integer times. Call a contiguous non-empty piece of the string even if every letter that occurs in it occurs exactly times times. Letters absent from the piece do not matter. Count the even pieces of text. Pieces with identical content but different starting positions are counted separately.

Example 1

text='xxyyxy', times=2 → 4

Four pieces qualify: "xx", "yy", "xxyy" and "xyyx". In "yyxy" the letter y appears three times, and in the two-letter "xy" and "yx" each letter appears only once.

Example 2

text='mmmm', times=2 → 3

The piece "mm" occurs at three positions. The whole string does not count: it has four m's, not two.

Example 3

text='abcabc', times=2 → 1

Constraints

1 ≤ len(text) ≤ 3·10⁴
1 ≤ times ≤ 3·10⁴
text consists only of lowercase English letters

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Hash Table String Counting Sliding Window

Similar problems

A Single-Letter Piece Seen Three Times Medium A Single-Letter Piece Seen Three Times: Long Text Medium Triples Without Repeats Easy Longest Repeat-Free Stretch Medium Two-Letter Stretch Medium

Input

text='xxyyxy', times=2

Expected

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