MLE '19 Contest 2 P1 - FUN


Submit solution

Points: 7 (partial)
Time limit: 3.0s
Memory limit: 128M

Author:
Problem type

A string is fun if it contains each character at most \(K\) times. Given a string \(S\), how many substrings of the string are fun? A substring is a non-empty contiguous sequence of characters within a string.

Input Specification

The first line will contain the string \(S\) \((1 \le |S| \le 10^5)\). The string will only consist of lowercase latin characters.

The second line will contain the integer \(K\) \((1 \le K \le |S|)\).

Output Specification

Output the number of substrings that are considered fun.

Subtasks

Subtask 1 [10%]

\(|S| \le 20\)

Subtask 2 [20%]

\(S\) will only contain the characters a and b.

Subtask 3 [70%]

No further constraints.

Sample Input 1 (Subtask 1)

abcabca
2

Sample Output 1

27

Sample Input 2 (Subtask 2)

aaaaaaaaaabbbbbbbbbba
2

Sample Output 2

45

Sample Input 3 (Subtask 3)

abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz
1

Sample Output 3

1027

Comments

There are no comments at the moment.