Skip to content

Latest commit

 

History

History
225 lines (176 loc) · 7.57 KB

README.md

File metadata and controls

225 lines (176 loc) · 7.57 KB
comments difficulty edit_url rating source tags
true
中等
1764
第 389 场周赛 Q3
贪心
哈希表
字符串
计数
排序

3085. 成为 K 特殊字符串需要删除的最少字符数

English Version

题目描述

给你一个字符串 word 和一个整数 k。

如果 |freq(word[i]) - freq(word[j])| <= k 对于字符串中所有下标 i 和 j  都成立，则认为 word 是 k 特殊字符串。

此处，freq(x) 表示字符 x 在 word 中的出现频率，而 |y| 表示 y 的绝对值。

返回使 word 成为 k 特殊字符串 需要删除的字符的最小数量。

 

示例 1：

输入：word = "aabcaba", k = 0

输出：3

解释：可以删除 2 个 "a" 和 1 个 "c" 使 word 成为 0 特殊字符串。word 变为 "baba"，此时 freq('a') == freq('b') == 2。

示例 2：

输入：word = "dabdcbdcdcd", k = 2

输出：2

解释：可以删除 1 个 "a" 和 1 个 "d" 使 word 成为 2 特殊字符串。word 变为 "bdcbdcdcd"，此时 freq('b') == 2，freq('c') == 3，freq('d') == 4。

示例 3：

输入：word = "aaabaaa", k = 2

输出：1

解释：可以删除 1 个 "b" 使 word 成为 2特殊字符串。因此，word 变为 "aaaaaa"，此时每个字母的频率都是 6。

 

提示：

  • 1 <= word.length <= 105
  • 0 <= k <= 105
  • word 仅由小写英文字母组成。

解法

方法一：计数 + 枚举

我们可以先统计字符串中每个字符的出现次数，将所有次数放入数组 $nums$ 中，由于题目中字符串只包含小写字母，所以数组 $nums$ 的长度不会超过 $26$。

接下来，我们可以枚举在 $[0,..n]$ 的范围内枚举 $K$ 特殊字符串中的字符最小频率 $v$，然后用一个函数 $f(v)$ 来计算将所有字符的频率调整为 $v$ 的最小删除次数，最后取所有 $f(v)$ 的最小值即为答案。

函数 $f(v)$ 的计算方法如下：

遍历数组 $nums$ 中的每个元素 $x$，如果 $x \lt v$，则说明我们需要将出现次数为 $x$ 的字符全部删除，删除次数为 $x$；如果 $x \gt v + k$，则说明我们需要将出现次数为 $x$ 的字符全部调整为 $v + k$，删除次数为 $x - v - k$。累加所有删除次数即为 $f(v)$ 的值。

时间复杂度 $O(n \times |\Sigma|)$，空间复杂度 $O(|\Sigma|)$。其中 $n$ 为字符串长度；而 $|\Sigma|$ 为字符集大小，本题中 $|\Sigma| = 26$。

Python3

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))

Java

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;
    }
}

C++

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;
    }
};

Go

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
}