3085: Minimum-Deletions-to-Make-String-K-Special
Medium

table of contents

We can reword this question.

In this question, there are 26 letters with varying frequency: n_1, n_2, n_3, …, n_26

For the OPTIMAL solution, we know that we want to set all the existing letters to a frequency of T. Intuitively, T should be equal to one of n_1, n_2, n_3, …, n_26.

We can demonstrate this with a simple example:

Let T = n_1 = 100 and say none of the ns are equal to 99. For T = 100, say there are a_1 letters with frequency greater than 100 + k and a_2 letters with frequency smaller than 100.

However, if we were to take T = 99,

meaning, overall this takes a_1 more deletions.

Then, we can iterate through all the letters in alphabet with index i, alphabet[i], and set it as the target. Now, when we re-iterate through alphabet with index j, if i != j, we have:

Then, we simply find the optimal alphabet[i] to set as the target and simply return the number of deletions made in total.

code

class Solution {
public:
    int minimumDeletions(string word, int k) {
        int alphabet[26] = {0};
        for (char c : word) {
            ++alphabet[c-'a'];
        }
        int ans = INT32_MAX;
        for (int i = 0; i < 26; ++i) {
            if (alphabet[i] == 0) continue;
            int currAns = 0;
            for (int j = 0; j < 26; ++j) {
                if (i == j) continue;
                
                if (alphabet[j] > alphabet[i]+k) {
                    currAns += alphabet[j]-alphabet[i]-k;
                }
                if (alphabet[j] < alphabet[i]) {
                    currAns += alphabet[j];
                }
            }
            ans = min(ans, currAns);
        }
        return ans;
    }
};

complexity

time taken