Somebody tell Lil Nas X
We call a string of length () a "" if there exists a subsequence of elements with indices , where such that for any , , and are distinct.
For example, for , the string abecc
is a "", because the subsequence ac
satisfies the condition described above (a
and c
are distinct).
Task
For a given string of length and a number , find how many substrings are "".
Input data
The first line contains the natural numbers and . The second line contains the string .
Output data
The first line will contain a single integer, representing the number of substrings that are "".
Constraints and clarifications
- ;
- ;
# | Points | Constraints |
---|---|---|
1 | 9 | |
2 | 16 | |
3 | 11 | It is guaranteed that , , and for , at least one of and is equal to |
4 | 27 | |
5 | 37 | No additional constraints |
, 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 "" substrings, of them being abecc
, be
, abe
.
Example 2
stdin
8 2
axbbcdde
stdout
11
Explanation
There are "" substrings, of them being axbbcdd
, xbbcd
, bbcdde
, and cdde
.
Example 3
stdin
8 3
axbbcdde
stdout
2
Explanation
The only "" substrings are axbbcdde
and xbbcdde
.