Minimum Deletions to Make String K-Special

Description

You are given a string word and an integer k.

We consider word to be k-special if |freq(word[i]) - freq(word[j])| <= k for all indices i and j in the string.

Here, freq(x) denotes the

frequency

of the character x in word, and |y| denotes the absolute value of y.

Return the minimum number of characters you need to delete to make word k-special.

Example 1:

Input: word = “aabcaba”, k = 0

Output: 3

Explanation: We can make word 0-special by deleting 2 occurrences of "a" and 1 occurrence of "c". Therefore, word becomes equal to "baba" where freq('a') == freq('b') == 2.

Example 2:

Input: word = “dabdcbdcdcd”, k = 2

Output: 2

Explanation: We can make word 2-special by deleting 1 occurrence of "a" and 1 occurrence of "d". Therefore, word becomes equal to “bdcbdcdcd” where freq('b') == 2, freq('c') == 3, and freq('d') == 4.

Example 3:

Input: word = “aaabaaa”, k = 2

Output: 1

Explanation: We can make word 2-special by deleting 1 occurrence of "b". Therefore, word becomes equal to "aaaaaa" where each letter’s frequency is now uniformly 6.

Constraints:

• 1 <= word.length <= 105
• 0 <= k <= 105
• word consists only of lowercase English letters.

Code

Time Complexity: $O(N^2)$, Space Complexity: $O(N)$

一開始解不出來主要的疑點在於：該怎麼決定上下界，在想怎麼樣移動 sliding window。

KEY：固定一個端點，大幅簡化問題，固定 minimum frequency，然後 iterate all，就可以了。

class Solution {
public:
    int minimumDeletions(string word, int k) {
        vector<int> frequencies(26, 0);
        for(auto& c: word) {
            frequencies[c - 'a']++;
        }
 
        int res = INT_MAX;
        for(int minFre: frequencies) {
            int deletions = 0;
            for(int fre: frequencies) {
                deletions += fre < minFre ? fre : max(0, fre - (minFre + k));
            }
            res = min(res, deletions);
        }
        return res;
    }
};

Source

• Minimum Deletions to Make String K-Special - LeetCode