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/A

N/A

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