strinK

Time limit: 0.04s Memory limit: 64MB Input: Output:

Somebody tell Lil Nas X

We call a string ss of length NN (2KN2 \cdot K \leq N) a "strinKstrinK" if there exists a subsequence of 2K2 \cdot K elements with indices i1,i2,i3,...,i2Ki_1, i_2, i_3, ..., i_{2 \cdot K}, where 1i1<i2<i3<...<i2KN1 \leq i_1 < i_2 < i_3 < ... < i_{2 \cdot K} \leq N such that for any jj, 1jK1 \leq j \leq K, si2j1s_{i_{2 \cdot j - 1}} and si2js_{i_{2 \cdot j}} are distinct.

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

Task

For a given string ss of length NN and a number KK, find how many substrings are "strinKstrinK".

Input data

The first line contains the natural numbers NN and KK. The second line contains the string ss.

Output data

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

Constraints and clarifications

  • 1K51051 \leq K \leq 5 \cdot 10^5;
  • 2KN1062 \cdot K \leq N \leq 10^6;
# Points Constraints
1 9 N100N \leq 100
2 16 N2 000N \leq 2\ 000
3 11 It is guaranteed that s1=s2s_1=s_2, sN=sN1s_N=s_{N-1}, and for 2iN12 \leq i \leq N-1, at least one of si1s_{i-1} and si+1s_{i+1} is equal to sis_i
4 27 N105N \leq 10^5
5 37 No additional constraints

Attention!\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 99 "strinKstrinK" substrings, 33 of them being abecc, be, abe.

Example 2

stdin

8 2
axbbcdde

stdout

11

Explanation

There are 1111 "strinKstrinK" substrings, 44 of them being axbbcdd, xbbcd, bbcdde, and cdde.

Example 3

stdin

8 3
axbbcdde

stdout

2

Explanation

The only 22 "strinKstrinK" substrings are axbbcdde and xbbcdde.

Log in or sign up to be able to send submissions!