Preparing NOJ

Equality

2000ms 262144K

Description:

You are given a string $$$s$$$ of length $$$n$$$, which consists only of the first $$$k$$$ letters of the Latin alphabet. All letters in string $$$s$$$ are uppercase.

A subsequence of string $$$s$$$ is a string that can be derived from $$$s$$$ by deleting some of its symbols without changing the order of the remaining symbols. For example, "ADE" and "BD" are subsequences of "ABCDE", but "DEA" is not.

A subsequence of $$$s$$$ called good if the number of occurences of each of the first $$$k$$$ letters of the alphabet is the same.

Find the length of the longest good subsequence of $$$s$$$.

Input:

The first line of the input contains integers $$$n$$$ ($$$1\le n \le 10^5$$$) and $$$k$$$ ($$$1 \le k \le 26$$$).

The second line of the input contains the string $$$s$$$ of length $$$n$$$. String $$$s$$$ only contains uppercase letters from 'A' to the $$$k$$$-th letter of Latin alphabet.

Output:

Print the only integer — the length of the longest good subsequence of string $$$s$$$.

Sample Input:

9 3
ACAABCCAB

Sample Output:

6

Sample Input:

9 4
ABCABCABC

Sample Output:

0

Note:

In the first example, "ACBCAB" ("ACAABCCAB") is one of the subsequences that has the same frequency of 'A', 'B' and 'C'. Subsequence "CAB" also has the same frequency of these letters, but doesn't have the maximum possible length.

In the second example, none of the subsequences can have 'D', hence the answer is $$$0$$$.

Info

CodeForces

Provider CodeForces

Origin Codeforces Round #508 (Div. 2)

Code CF1038A

Tags

implementationstrings

Submitted 50

Passed 32

AC Rate 64%

Date 03/04/2019 16:35:35

Related

Nothing Yet