Skip to content

3085. Minimum Deletions to Make String K-Special

SourceWeekly Contest 389 Q3DifficultyMediumRating1764

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.

Solutions

Solution 1: Counting + Enumeration

Thinking

Every remaining pair of frequencies may differ by at most \(k\). We may only delete, \(n \le 10^5\), and there are \(26\) letters.

Kept frequencies lie in some interval \([v,v+k]\). Letters below \(v\) are deleted entirely; those above \(v+k\) are cut down to \(v+k\).

We enumerate the smallest kept frequency \(v\) and take the minimum of that sum over the \(26\) counts.

First, we can count the occurrence of each character in the string and put all the counts into an array \(nums\). Since the string only contains lowercase letters, the length of the array \(nums\) will not exceed \(26\).

Next, we can enumerate the minimum frequency \(v\) of characters in the \(K\) special strings within the range \([0,..n]\), and then use a function \(f(v)\) to calculate the minimum number of deletions to adjust the frequency of all characters to \(v\). The minimum value of all \(f(v)\) is the answer.

The calculation method of function \(f(v)\) is as follows:

Traverse each element \(x\) in the array \(nums\). If \(x < v\), it means that we need to delete all characters with a frequency of \(x\), and the number of deletions is \(x\). If \(x > v + k\), it means that we need to adjust all characters with a frequency of \(x\) to \(v + k\), and the number of deletions is \(x - v - k\). The sum of all deletion counts is the value of \(f(v)\).

The time complexity is \(O(n \times |\Sigma|)\), and the space complexity is \(O(|\Sigma|)\). Here, \(n\) is the length of the string, and \(|\Sigma|\) is the size of the character set. In this problem, \(|\Sigma| = 26\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def minimumDeletions(self, word: str, k: int) -> int:
        def f(v: int) -> int:
            ans = 0
            for x in nums:
                if x < v:
                    ans += x
                elif x > v + k:
                    ans += x - v - k
            return ans

        nums = Counter(word).values()
        return min(f(v) for v in range(len(word) + 1))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    private List<Integer> nums = new ArrayList<>();

    public int minimumDeletions(String word, int k) {
        int[] freq = new int[26];
        int n = word.length();
        for (int i = 0; i < n; ++i) {
            ++freq[word.charAt(i) - 'a'];
        }
        for (int v : freq) {
            if (v > 0) {
                nums.add(v);
            }
        }
        int ans = n;
        for (int i = 0; i <= n; ++i) {
            ans = Math.min(ans, f(i, k));
        }
        return ans;
    }

    private int f(int v, int k) {
        int ans = 0;
        for (int x : nums) {
            if (x < v) {
                ans += x;
            } else if (x > v + k) {
                ans += x - v - k;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    int minimumDeletions(string word, int k) {
        int freq[26]{};
        for (char& c : word) {
            ++freq[c - 'a'];
        }
        vector<int> nums;
        for (int v : freq) {
            if (v) {
                nums.push_back(v);
            }
        }
        int n = word.size();
        int ans = n;
        auto f = [&](int v) {
            int ans = 0;
            for (int x : nums) {
                if (x < v) {
                    ans += x;
                } else if (x > v + k) {
                    ans += x - v - k;
                }
            }
            return ans;
        };
        for (int i = 0; i <= n; ++i) {
            ans = min(ans, f(i));
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func minimumDeletions(word string, k int) int {
    freq := [26]int{}
    for _, c := range word {
        freq[c-'a']++
    }
    nums := []int{}
    for _, v := range freq {
        if v > 0 {
            nums = append(nums, v)
        }
    }
    f := func(v int) int {
        ans := 0
        for _, x := range nums {
            if x < v {
                ans += x
            } else if x > v+k {
                ans += x - v - k
            }
        }
        return ans
    }
    ans := len(word)
    for i := 0; i <= len(word); i++ {
        ans = min(ans, f(i))
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function minimumDeletions(word: string, k: number): number {
    const freq: number[] = Array(26).fill(0);
    for (const ch of word) {
        ++freq[ch.charCodeAt(0) - 97];
    }
    const nums = freq.filter(x => x > 0);
    const f = (v: number): number => {
        let ans = 0;
        for (const x of nums) {
            if (x < v) {
                ans += x;
            } else if (x > v + k) {
                ans += x - v - k;
            }
        }
        return ans;
    };
    return Math.min(...Array.from({ length: word.length + 1 }, (_, i) => f(i)));
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
impl Solution {
    pub fn minimum_deletions(word: String, k: i32) -> i32 {
        let mut freq = [0; 26];
        for c in word.chars() {
            freq[(c as u8 - b'a') as usize] += 1;
        }
        let mut nums = vec![];
        for &v in freq.iter() {
            if v > 0 {
                nums.push(v);
            }
        }
        let n = word.len() as i32;
        let mut ans = n;
        for i in 0..=n {
            let mut cur = 0;
            for &x in nums.iter() {
                if x < i {
                    cur += x;
                } else if x > i + k {
                    cur += x - i - k;
                }
            }
            ans = ans.min(cur);
        }
        ans
    }
}

Comments