Stringforces
题意翻译
- 设 $s$ 是一个由前 $k$ 个小写字母构成的字符串,$v$ 是前 $k$ 个小写字母中的某一个。定义 $\mathrm{MaxLen}(s,v)$ 表示 $s$ 所有仅由字母 $v$ 构成的连续子串的最长长度。
- 定义 $s$ 的价值为所有 $\mathrm{MaxLen}(S,v)$ 的最小值,其中 $v$ 取遍前 $k$ 个小写字母。
- 现在给定一个长度为 $n$ 的字符串 $s$,$s$ 中字母要么是前 $k$ 个小写字母中的某一个,要么是问号。你需要将 $s$ 中的每一个问号替换成前 $k$ 个小写字母中的一个,并最大化 $s$ 的价值。方便起见,你只需要输出这个最大的价值即可。
- 保证 $1\leq n\leq 2\times 10^5$,$1\leq k\leq 17$。
题目描述
You are given a string $ s $ of length $ n $ . Each character is either one of the first $ k $ lowercase Latin letters or a question mark.
You are asked to replace every question mark with one of the first $ k $ lowercase Latin letters in such a way that the following value is maximized.
Let $ f_i $ be the maximum length substring of string $ s $ , which consists entirely of the $ i $ -th Latin letter. A substring of a string is a contiguous subsequence of that string. If the $ i $ -th letter doesn't appear in a string, then $ f_i $ is equal to $ 0 $ .
The value of a string $ s $ is the minimum value among $ f_i $ for all $ i $ from $ 1 $ to $ k $ .
What is the maximum value the string can have?
输入输出格式
输入格式
The first line contains two integers $ n $ and $ k $ ( $ 1 \le n \le 2 \cdot 10^5 $ ; $ 1 \le k \le 17 $ ) — the length of the string and the number of first Latin letters used.
The second line contains a string $ s $ , consisting of $ n $ characters. Each character is either one of the first $ k $ lowercase Latin letters or a question mark.
输出格式
Print a single integer — the maximum value of the string after every question mark is replaced with one of the first $ k $ lowercase Latin letters.
输入输出样例
输入样例 #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
说明
In the first example the question marks can be replaced in the following way: "aaaababbbb". $ f_1 = 4 $ , $ f_2 = 4 $ , thus the answer is $ 4 $ . Replacing it like this is also possible: "aaaabbbbbb". That way $ f_1 = 4 $ , $ f_2 = 6 $ , however, the minimum of them is still $ 4 $ .
In the second example one of the possible strings is "aabbccdda".
In the third example at least one letter won't appear in the string, thus, the minimum of values $ f_i $ is always $ 0 $ .