Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Beautiful Subsequences

By mridul_sust · Limits 1s, 512 MB

You are given a string. You have to find the number of beautiful subsequences in the string.

A subsequence is a sequence of characters that can be derived from a string by deleting some characters without changing the order of the remaining characters. For example, “abba” is a subsequence in “bacbdeba”, but “bbaa” is not.

Beauty of a character is the sum of positions of that character in the string. For example, beauty of ‘a’ in the string “bacbdeba” is $2+8 = 10$, becuase the positions of ‘a’ in the string are $2$ and $8$. Beauty of a subsequence is the sum of beauties of the characters in the subsequence. For example, the beauty of the subsequence “aa” of string “bacbdeba” is $10+10 = 20$.

A subsequence is beautiful, if both of the following conditions hold.

1. If you include a character to a subsequence, you should include all of its occurences. For example, for the string “bacbdeba”, “babba” can be beautiful (if it obeys the other condition), but “ba” can not be. Because, if ‘b’ is chosen to be in the subsequence, all occurrences of ‘b’ in the string should be in the subsequence, same for ‘a’.
2. Beauty of the subsequence should be at least M.

You are given a string of length N. Can you find how many beautiful subsequences can be derived from the string?

Input

The first line of the input contains two integers $N$ and $M$. The next line contains the string. The string contains lowercase English letters (‘a’ to ‘z’ ) and digits (‘0’ to ‘9’ ).

$1 ≤ N ≤ 10^5 $
$1 ≤ M ≤ 10^9 $

Output

Print an integer in a single line denoting the number of beautiful subsequences.

Samples

InputOutput
2 2
aa
1
InputOutput
3 5
a1a
2

For the first case, “aa” is the only beautiful subsequence.
For the second case, “aa” and “a1a” are the two beautiful subsequences

    Discussion

    Statistics


    67% Solution Ratio

    fsshakkhorEarliest, 1M ago

    Ashraful_jnuFastest, 0.0s

    Ashraful_jnuLightest, 262 kB

    mijanurShortest, 949B

    Submit

    Login to submit