Skip to content

← leetcode

Minimum Deletions to Make String K Special

· Medium

LeetCode problem 3085

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.

  • we have to decrement a_1 letters to 100 + k frequency
  • we have to decrement a_2 letters to 0 frequency

However, if we were to take T = 99,

  • we still have to decrement a_1 letters, however, this time it is to 99 + k frequency
  • we still have to decrement a_2 letters to 0 frequency

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:

  • alphabet[j] < target, meaning we have to make alphabet[j] number of deletions
  • alphabet[j] > target + k, meaning we have to make alphabet[j] - (target + k) number of deletions

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: O(n) where n is the size of word
  • Space: 'O(1)

time taken

  • 19 minutes and 28 seconds
    • but I like fell asleep on the bus so this does not count-