Preparing NOJ

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

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.

Print the only integerÂ â€” the length of the longest good subsequence of string $$$s$$$.

9 3

ACAABCCAB

6

9 4

ABCABCABC

0

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

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