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 its 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 than ~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|)~?