← 返回题目列表

Codeforces · 1038/A

A. 平等

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$,该字符串仅包含拉丁字母表中的前 $$$k$$$ 个字母。字符串 $$$s$$$ 中的所有字母均为大写。

字符串 $$$s$$$ 的子序列是可以通过删除 $$$s$$$ 的一些符号而不更改其余符号的顺序来从 $$$s$$$ 派生的字符串。例如,“ADE”和“BD”是“ABCDE”的子序列,但“DEA”不是。

如果字母表中前 $$$k$$$ 个字母的出现次数相同,则 $$$s$$$ 的子序列称为良好。

求 $$$s$$$ 的最长好子序列的长度。

输入

输入的第一行包含整数 $$$n$$$ ($$$1\le n \le 10^5$$$) 和 $$$k$$$ ($$$1 \le k \le 26$$$)。

输入的第二行包含长度为 $$$n$$$ 的字符串 $$$s$$$。字符串 $$$s$$$ 仅包含从 'A' 到拉丁字母表中第 $$$k$$$ 的大写字母。

输出

打印唯一的整数——字符串 $$$s$$$ 的最长好子序列的长度。

示例

输入 #1

9 3
ACAABCCAB

输出 #1

6

输入 #2

9 4
ABCABCABC

输出 #2

0

注意

在第一个示例中,“ACBCAB”(“ACAABCCAB”)是具有相同频率“A”、“B”和“C”的子序列之一。子序列“CAB”也具有相同的这些字母的频率,但没有最大可能的长度。

在第二个示例中,所有子序列都不能包含“D”,因此答案为 $$$0$$$。