Stringforces
Contest: Educational Codeforces Round 111 (Rated for Div. 2)
Difficulty rating: 2500
Tags: binary search, bitmasks, brute force, dp, strings, two pointers

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?

Input format:
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.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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

Example input:
10 2
a??ab????b

Example output:
4

Example input:
9 4
?????????

Example output:
2

Editorial:
Notice that if there are substrings of length $$$x$$$ for each letter, then there are also substrings of length $$$x-1$$$. Thus, the function on the answer is monotonous, so the binary search is applicable.
Let's have some answer $$$x$$$ fixed by binary search. We have to place $$$k$$$ blocks of letters of length $$$x$$$ somewhere in a string. If we fix an order these blocks go into the string, then the greedy algorithm for placing them works. Put each block after the previous one but as far to the left as possible (the correctness can be proven by showing that picking not the furthest to the left position can't be more optimal). If there exists such an order that all blocks fit, then the answer is greater than or equal to $$$x$$$.
The common transition is to move from iterating over permutations to dynamic programming over submasks. Let $$$dp[mask]$$$ be the smallest prefix of the string, such that all blocks of letters from the mask fit into this prefix. The transitions are the same: pick a new block and place it as early after that prefix as possible.
So far the solution works pretty slow, since for each of $$$2^k$$$ masks we have to find the earliest possible position for a block. Let's use some precalculations to perform the transitions in $$$O(1)$$$.
Notice that the transition doesn't depend on a mask, only on a length of the previous prefix. Thus, for every prefix and every letter, we can save the closest position for a block.
Let $$$pos[i][j]$$$ be the closest position for a prefix of length $$$i$$$ and the $$$j$$$-th letter. $$$pos[i][j]$$$ is at least equal to $$$pos[i + 1][j]$$$. However, if the block can be placed at the $$$i$$$-th position, then it should be updated. That can happen if the closest occurrence of any letter except $$$j$$$ is not smaller than $$$j + x$$$. Thus, we can also maintain the closest occurrence of every letter. With some smart iterations, we can do the precalculations in $$$O(nk)$$$.
The dynamic programming works in $$$O(2^k \cdot k)$$$ then.
Overall complexity: $$$O((nk + 2^k \cdot k) \log n)$$$.