A14424 | 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?

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.