Editorial for Back From Summer '19 P3: ASDFGHJKL


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: wleung_bvg

Subtask 1

For the first subtask, we only need to worry about removing individual characters from the original string. Observe that for each of the K 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 \mathcal{O}(|S|) and do the following K times: find the most frequent letter and decrement it's frequency in the array. After doing this K times, we can compute the minimum value using the resulting frequency array.

Time Complexity: \mathcal{O}(|S|)

Subtask 2

For the second subtask, we can see that there are |S| - L + 1 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 K individual characters, however the method used in subtask 1 will be too slow. Instead, we can observe that after removing K letters, there exists a value x such that all letters that originally had a frequency of greater that x (after removing the substring), now have a frequency of x or x - 1. We can binary search for this value of x by checking to see if the sum of the remaining letters is less than or equal to |S| - L - K. We can then determine the frequencies of the letters for the minimum value string after removing K letters, for each possible substring that is removed. The answer is the global minimum among all possible candidates. Be careful when L + K > |S|, as you can remove the entire string.

Time Complexity: \mathcal{O}(|S| \log{|S|})

Bonus

Can you solve the problem in \mathcal{O}(|S|)?


Comments

There are no comments at the moment.