难度: Medium
Submission
运行时间: 41 ms
内存: 16.5 MB
class Solution:
def minimumKeypresses(self, s: str) -> int:
return sum([cnt*(i//9+1) for i, cnt in enumerate(sorted(Counter(s).values(), reverse=True))])
Explain
此题解的思路是首先统计字符串 s 中每个字符出现的次数，然后将这些次数按照从大到小的顺序排序。对于按键次数的计算，我们知道最常出现的字符应该尽可能少按键，因此我们将出现次数最多的字符放在按键次数最少的位置。具体地，字符的按键次数计算公式为 (索引 // 9 + 1)，意味着前9个最频繁的字符（索引0-8）需要按1次，接下来9个字符（索引9-17）需要按2次，依此类推。最终，将所有字符的按键次数与其出现次数的乘积加和，得到总的最少按键次数。
时间复杂度: O(n + m log m)
空间复杂度: O(m)
class Solution:
def minimumKeypresses(self, s: str) -> int:
# 计算每个字符的出现次数
char_counts = Counter(s)
# 对字符出现次数进行降序排序
sorted_counts = sorted(char_counts.values(), reverse=True)
# 计算每个字符的按键次数并求和
return sum(cnt * (i // 9 + 1) for i, cnt in enumerate(sorted_counts))
Explore
在该题解中，将字符出现次数进行降序排序是为了确保出现频率最高的字符被分配到按键次数最少的位置。这是因为频繁出现的字符如果按键次数较少，则可以显著减少总的按键次数。通过这种排序方式，可以将按键分配最优化，使得总的按键次数达到最小。
该计算公式`(索引 // 9 + 1)`是基于每9个字符一个按键次数等级来设计的。具体来说，索引从0开始，0到8的字符（共9个）需要按1次，索引9到17的下一组9个字符需要按2次，依此类推。这种分配方式确保了出现频率最高的字符（即排序后索引最小的字符）被分配到按键次数最少的组，从而在总的按键次数上实现最小化。
如果多个字符出现次数相同，它们在排序后的具体顺序对最终的总按键次数没有影响。这是因为相同频率的字符不论如何排序，它们最终被分配到的按键次数等级是相同的。因此，即使排序结果在相同频率字符之间有所不同，总按键次数仍将保持不变。