RoAlgo Contest #10 | strinK

Somebody tell Lil Nas X

We call a string $s$ of length $N$ ($2 \cdot K \leq N$) a "$strinK$" if there exists a subsequence of $2 \cdot K$ elements with indices $i_1, i_2, i_3, ..., i_{2 \cdot K}$, where $1 \leq i_1 < i_2 < i_3 < ... < i_{2 \cdot K} \leq N$ such that for any $j$, $1 \leq j \leq K$, $s_{i_{2 \cdot j - 1}}$ and $s_{i_{2 \cdot j}}$ are distinct.

For example, for $K=1$, the string $s=$ abecc is a "$strinK$", because the subsequence ac satisfies the condition described above (a and c are distinct).

Task

For a given string $s$ of length $N$ and a number $K$, find how many substrings are "$strinK$".

Input data

The first line contains the natural numbers $N$ and $K$. The second line contains the string $s$.

Output data

The first line will contain a single integer, representing the number of substrings that are "$strinK$".

Constraints and clarifications

• $1 \leq K \leq 5 \cdot 10^5$;
• $2 \cdot K \leq N \leq 10^6$;

$\bold{Attention!}$, the time limit during the contest was 0.1s, now it is 0.04s to encourage finding more efficient solutions. Contest submissions haven't been reevaluated

Example 1

stdin

5 1
abecc

stdout

9

Explanation

There are $9$ "$strinK$" substrings, $3$ of them being abecc, be, abe.

Example 2

stdin

8 2
axbbcdde

stdout

11

Explanation

There are $11$ "$strinK$" substrings, $4$ of them being axbbcdd, xbbcd, bbcdde, and cdde.

Example 3

stdin

8 3
axbbcdde

stdout

2

Explanation

The only $2$ "$strinK$" substrings are axbbcdde and xbbcdde.