algorithm - 如何找到使字符串平衡的最少操作数？

Question

来自 Codechef :

A string is considered balanced if and only if all the characters occur in it equal number of times.

You are given a string S; this string may only contain uppercase English letters. You may perform the following operation any number of times (including zero): Choose one letter in S and replace it by another uppercase English letter. Note that even if the replaced letter occurs in S multiple times, only the chosen occurrence of this letter is replaced.

Find the minimum number of operations required to convert the given string to a balanced string.

Example:

For input: ABCB

Here, we can replace C with A, TO GET: ABAB, where each character of the string occurs for 2 times.

So, the number of minimum operation(s)=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 之间没有真正的区别，因为两者都可以通过用 A 替换其 C 来平衡.
• 对数组进行排序。对于您的示例，它给出了 [0, 0, ..., 0, 1, 1, 2]。
  • 我们可以这样做是因为我们实际上并不关心哪个字母是哪个； ABCB 和 ABDB 之间没有真正的区别，因为两者都可以通过将其中一个单独字母替换为另一个单独字母来实现平衡。
• 假设字符串不为空(因为如果它为空则答案仅为 0)，最终平衡的字符串将包含至少 1 个至多 26 个不同的字母。对于 1 到 26 之间的每个整数 i，确定您需要执行多少次操作才能生成具有 i 个不同字母的平衡字符串:
  • 首先，检查长度(S) 是i 的倍数；如果不是，这是不可能的，所以跳到下一个整数。
  • 接下来，计算^length(S)/_i，即最终平衡字符串中每个不同字母的计数。
  • 为了计算需要执行多少操作，我们将检查所有需要增加的计数。 (等效地，我们可以检查需要减少的计数:它们必须匹配。)
  • 我们只对排序数组的最后 i 个元素感兴趣。该点之前的任何元素表示不会出现在平衡字符串中的字母:计数已经为零并将保持为零，或者它们不为零但将减少为零。无论哪种方式，由于我们只跟踪增加，我们可以忽略它们。
  • 对于小于^length(S)/_i 的最后i 个计数，添加区别。这个总和就是操作数。 (请注意，由于计数已排序，您可以在计数大于或等于目标计数时立即退出此内部循环。)
  • 您可以在大于或等于原始 S 中不同字母数的第一个 i 之后退出此循环(i 的值除外 我们不得不跳过，因为它们没有平均划分长度 (S))。例如，如果 length(S) = 100，并且原始 S 有 19 个不同的字母，那么我们只需要将 i 视为高为 20。(向 Eric Wang 致敬，因为他们提出了类似的建议。)
• 返回这些最多 26 个总和中的最小值。 (请注意，您实际上不需要存储所有总和；您只需跟踪最小值即可。)