假设我们有一个字符串 s,如果 s 中没有两个不同的字符频率相同,则称 s 是好的。我们必须找到需要删除的最少字符数才能生成一个好的字符串。
因此,如果输入类似于 s = "ssstttuu",那么输出将是 2,因为如果我们删除一个 't',那么将有三个 's'、两个 't' 和两个 'u',然后再次删除一个,“t”或“u”,使它们变得更好。
让我们看看以下实现以获得更好的理解 -
from collections import Counter def solve(s): val = Counter(s) res = 0 numlist = sorted([i for i in val.values()]) for i in range(len(numlist)-1): if numlist[i] and numlist[i] == numlist[i+1]: numlist[i] -= 1 res += 1 k = i-1 m = i while numlist[m] and numlist[m] == numlist[k]: numlist[k] -= 1 k -= 1 m -= 1 res += 1 return res s = "ssstttuu" print(solve(s))
"ssstttuu"输出结果
2