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=102+8 = 10, becuase the positions of 'a' in the string are 22 and 88. 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=2010+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?


The first line of the input contains two integers NN and MM.
The next line contains the string. The string contains lowercase English letters ('a' to 'z' ) and digits ('0' to '9' ).

1N1051 ≤ N ≤ 10^5
1M1091 ≤ M ≤ 10^9


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


2 2
3 5

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, Aug '20

    Ashraful_jnuFastest, 0.0s

    Ashraful_jnuLightest, 262 kB

    mijanurShortest, 949B


    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.