如何找到使字符串平衡的最小操作次数？

Question

来自Codechef:

当且仅当所有字符在其中出现相同的次数时,才认为字符串是平衡的.

给你一个字符串S; 此字符串可能只包含大写英文字母.您可以多次执行以下操作(包括零):选择一个字母S并用另一个大写英文字母替换它.请注意,即使被替换的字母S多次出现,也只会替换此字母的所选出现.

找到将给定字符串转换为平衡字符串所需的最少操作数.

例:

输入: ABCB

在这里,我们可以替换C为ATO GET:,ABAB其中字符串的每个字符出现2次.

所以,最小操作次数= 1.

如何使弦好？

我可以应用动态编程吗？

Answer 1

我认为你真的不需要动态编程.

O(长度(S))时间的一种方法:

• 迭代S,构建频率图(从不同字母A-Z到计数的映射).对于您的ABCB示例,那将是A->1 B->2 C->1 D->0 E->0 ... Z->0,我们可以表示为数组[1, 2, 1, 0, 0, ..., 0].
  • 我们可以这样做,因为我们实际上并不关心字母的位置; ABCB和之间没有真正的区别ABBC,因为每个都可以C用一个替换它们来平衡A.
• 对数组进行排序.对于你的例子,这给出了[0, 0, ..., 0, 1, 1, 2].
  • 我们可以这样做,因为我们实际上并不关心哪个字母是哪个; ABCB和之间没有真正的区别ABDB,因为可以通过用另一个单个字母替换它们中的一个来平衡每一个.
• 假设字符串是非空的(因为如果它是答案只是0),最终的平衡字符串将包含至少1个,最多26个不同的字母.对于1到26之间的每个整数i,确定为了生成具有i个不同字母的平衡字符串需要执行的操作数:
  • 首先,检查长度(S)是i的倍数; 如果没有,这是不可能的,所以跳到下一个整数.
  • 接下来,计算^长度(S)/_i,即最终平衡字符串中每个不同字母的计数.
  • 为了计算需要执行的操作数量,我们将检查需要增加的所有计数.(我们可以等同地检查需要减少的计数:它们必须匹配.)
  • 我们只对排序数组的最后一个i元素感兴趣.该点之前的任何元素表示不会出现在平衡字符串中的字母:计数已经为零并且将保持为零,或者它们非零但将减少为零.无论哪种方式,由于我们只跟踪增加,我们可以忽略它们.
  • 对于小于^长度(S)/_i的最后一个i计数中的每一个,添加差异.该总和是操作的数量.(请注意,由于计数已排序,因此只要计数大于或等于目标计数,就可以退出此内循环.)
  • 您可以在第一个i之后退出此循环,该第一个i大于或等于原始S中不同字母的数量(除了我们必须跳过的i的值,因为它们不能均匀地划分长度(S)).例如,如果长度(S)= 100,并且原始S有19个不同的字母,那么我们只需要考虑我高达20个.(对于Eric Wang来说,建议沿着这些线条提供一些东西.)
• 返回这些最多26个总和.(请注意,您实际上并不需要存储所有总和;您可以跟踪最小值.)