CF1550E.Stringforces

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?

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

你需要将每个问号替换为前 $k$ 个小写拉丁字母中的某一个，使得以下值最大化。

令 $f_i$ 表示字符串 $s$ 中由第 $i$ 个拉丁字母完全组成的最长子串的长度。字符串的子串是指该字符串的一个连续子序列。若第 $i$ 个字母未在字符串中出现，则 $f_i = 0$。

字符串 $s$ 的值定义为所有 $i$（从 $1$ 到 $k$）对应的 $f_i$ 中的最小值。

该字符串所能达到的最大值是多少？

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.

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$；$1 \le k \le 17$）—— 分别表示字符串的长度以及所使用的前 $k$ 个拉丁字母的数量。

第二行包含一个长度为 $n$ 的字符串 $s$。其中每个字符要么是前 $k$ 个小写拉丁字母之一，要么是一个问号。

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.

输出一个整数——在将每个问号替换为前 $k$ 个小写拉丁字母中的一个后，字符串所能达到的最大值。

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$.

在第一个例子中，问号可以如下替换：“aaaababbbb”。此时 $f_1 = 4$，$f_2 = 4$，因此答案为 $4$。也可以按如下方式替换：“aaaabbbbbb”，此时 $f_1 = 4$，$f_2 = 6$，但它们的最小值仍为 $4$。

在第二个例子中，一种可能的字符串是 “aabbccdda”。

在第三个例子中，至少有一个字母不会出现在字符串中，因此所有 $f_i$ 值的最小值恒为 $0$。