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

样例输入 #1

10 2
a??ab????b

样例输出 #1

4

样例 #2

样例输入 #2

9 4
?????????

样例输出 #2

2

样例 #3

样例输入 #3

2 3
??

样例输出 #3

0

样例 #4

样例输入 #4

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

样例输出 #4

3

样例 #5

样例输入 #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$ .