# Practice on Toph

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

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

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

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 $`

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

Input | Output |
---|---|

2 2 aa | 1 |

Input | Output |
---|---|

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

67% Solution Ratio

fsshakkhorEarliest,

Ashraful_jnuFastest, 0.0s

Ashraful_jnuLightest, 262 kB

mijanurShortest, 949B

Login to submit