字符频次唯一的最小删除次数

核心就一句:频次撞车就往下退一格,退到空位为止;退几格就删几个。下面每一帧都在套这套规则。

先统计:a、b、c 都出现 5 次,d、e 都出现 2 次。下面每个柱子上的数字就是该字符的频次,我们要把这些数字调成两两不同。

轮到字符 a(紫色),它现在出现 5 次。看看频次 5 是否已被前面的字符占用。

频次 5 还没人占,a 就定在 5(变绿,加进右侧「已占用」)。a 处理完毕,继续下一个字符。

轮到字符 b(紫色),它现在出现 5 次。看看频次 5 是否已被前面的字符占用。

频次 5 已经在「已占用」里(右侧高亮),b 不能也用 5。删掉一个 b,频次降到 4。

删除计数变成 1。b 现在频次 4,继续看 4 是否被占用。

频次 4 还没人占,b 就定在 4(变绿,加进右侧「已占用」)。b 处理完毕,继续下一个字符。

轮到字符 c(紫色),它现在出现 5 次。看看频次 5 是否已被前面的字符占用。

频次 5 已经在「已占用」里(右侧高亮),c 不能也用 5。删掉一个 c,频次降到 4。

删除计数变成 2。c 现在频次 4,继续看 4 是否被占用。

频次 4 已经在「已占用」里(右侧高亮),c 不能也用 4。删掉一个 c,频次降到 3。

删除计数变成 3。c 现在频次 3,继续看 3 是否被占用。

频次 3 还没人占,c 就定在 3(变绿,加进右侧「已占用」)。c 处理完毕,继续下一个字符。

轮到字符 d(紫色),它现在出现 2 次。看看频次 2 是否已被前面的字符占用。

频次 2 还没人占,d 就定在 2(变绿,加进右侧「已占用」)。d 处理完毕,继续下一个字符。

轮到字符 e(紫色),它现在出现 2 次。看看频次 2 是否已被前面的字符占用。

频次 2 已经在「已占用」里(右侧高亮),e 不能也用 2。删掉一个 e,频次降到 1。

删除计数变成 4。e 现在频次 1,继续看 1 是否被占用。

频次 1 还没人占,e 就定在 1(变绿,加进右侧「已占用」)。e 处理完毕,继续下一个字符。

处理完所有字符,各字符频次变成 a:5、b:4、c:3、d:2、e:1,彼此都不相同。一路删了 4 个字符,这就是答案。

边界:单种字符永远 0;频次全撞一起时删得最多。

两个高频追问:顺序无关结果、排序写法等价。