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

目标

给你一个字符串 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 <= 10^5
  • 0 <= k <= 10^5
  • word 仅由小写英文字母组成。

思路

统计字符串中字符的频次,如果频次最大值减去频次最小值小于等于 k 则称为 k 特殊字符,计算使得字符串变为 k 特殊字符串最少需要删除多少个字符。

// todo

代码

性能