CF1550E Stringforces

给定一个长度为 $n$ 的字符串 $s$。每个字符要么是前 $k$ 个小写拉丁字母之一，要么是问号。 你需要将每个问号替换为前 $k$ 个小写拉丁字母中的某一个，使得下述值最大化。 令 $f_i$ 表示字符串 $s$ 中完全由第 $i$ 个拉丁字母组成的最长子串的长度。字符串的子串是该字符串的一个连续子序列。如果第 $i$ 个字母没有出现在字符串中，则 $f_i = 0$。 字符串 $s$ 的值定义为所有 $f_i$（$i$ 从 $1$ 到 $k$）中的最小值。 请问，在将所有问号替换为前 $k$ 个小写拉丁字母后，字符串的最大可能值是多少。

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^5$；$1 \le k \le 17$），分别表示字符串的长度和使用的前 $k$ 个拉丁字母的数量。 第二行包含一个长度为 $n$ 的字符串 $s$，每个字符要么是前 $k$ 个小写拉丁字母之一，要么是问号。

输出一个整数，表示在将所有问号替换为前 $k$ 个小写拉丁字母后，字符串的最大可能值。

在第一个样例中，问号可以替换为如下方式："aaaababbbb"。此时 $f_1 = 4$，$f_2 = 4$，因此答案为 $4$。也可以替换为："aaaabbbbbb"。此时 $f_1 = 4$，$f_2 = 6$，但它们的最小值仍然是 $4$。 在第二个样例中，其中一种可能的字符串为 "aabbccdda"。 在第三个样例中，至少有一个字母不会出现在字符串中，因此所有 $f_i$ 的最小值始终为 $0$。 由 ChatGPT 4.1 翻译