给定一个长度为 $$$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$$$。