Editorial for Back From Summer '19 P3: ASDFGHJKL
Submitting an official solution before solving the problem yourself is a bannable offence.
For the first subtask, we only need to worry about removing individual characters from the original string. Observe that for each of the removals, it is always optimal to remove the most frequent letter. Thus, we can build a frequency array of the count for each character in and do the following times: find the most frequent letter and decrement it's frequency in the array. After doing this times, we can compute the minimum value using the resulting frequency array.
For the second subtask, we can see that there are different substrings to remove. We can get the frequency of the remaining letters quickly by either using prefix sum arrays, or maintaining a sliding window. For each substring that is removed, we will compute the minimum value of the string after removing individual characters, however the method used in subtask 1 will be too slow. Instead, we can observe that after removing letters, there exists a value such that all letters that originally had a frequency of greater that (after removing the substring), now have a frequency of or . We can binary search for this value of by checking to see if the sum of the remaining letters is less than or equal to . We can then determine the frequencies of the letters for the minimum value string after removing letters, for each possible substring that is removed. The answer is the global minimum among all possible candidates. Be careful when , as you can remove the entire string.
Can you solve the problem in ?