← 返回题目列表

Codeforces · 1550/E

E. 弦力

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

给定一个长度为 $$$n$$$ 的字符串 $$$s$$$。每个字符要么是前 $$$k$$$ 小写拉丁字母之一,要么是问号。

您需要将每个问号替换为前 $$$k$$$ 小写拉丁字母之一,以使以下值最大化。

令 $$$f_i$$$ 为字符串 $$$s$$$ 的最大长度子串​​,它完全由第 $$$i$$$ 个拉丁字母组成。字符串的子字符串是该字符串的连续子序列。如果第 $$$i$$$ 个字母未出现在字符串中,则 $$$f_i$$$ 等于 $$$0$$$。

字符串$$$s$$$的值是$$$f_i$$$中从$$$1$$$到$$$k$$$的所有$$$i$$$中的最小值。

字符串的最大值是多少?

输入

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 17$$$) - 字符串的长度和使用的第一个拉丁字母的数量。

第二行包含字符串 $$$s$$$,由 $$$n$$$ 个字符组成。每个字符要么是前 $$$k$$$ 小写拉丁字母之一,要么是问号。

输出

打印单个整数 - 每个问号替换为前 $$$k$$$ 小写拉丁字母之一后的字符串最大值。

示例

输入 #1

10 2
a??ab????b

输出 #1

4

输入 #2

9 4
?????????

输出 #2

2

输入 #3

2 3
??

输出 #3

0

输入#4

15 3
??b?babbc??b?aa

输出#4

3

输入 #5

4 4
cabd

输出 #5

1

注意

在第一个示例中,问号可以用以下方式替换:“aaaabbabbbb”。 $$$f_1 = 4$$$,$$$f_2 = 4$$$,因此答案是$$$4$$$。像这样替换它也是可能的:“aaaabbbbbb”。这样$$$f_1 = 4$$$,$$$f_2 = 6$$$,但是,它们的最小值仍然是$$$4$$$。

在第二个示例中,可能的字符串之一是“aabbccdda”。

在第三个示例中,字符串中至少不会出现一个字母,因此 $$$f_i$$$ 的最小值始终为 $$$0$$$。