如何找到使字符串平衡的最小操作数？ [英] How to find the minimum number of operation(s) to make the string balanced?

问题描述

来自 Codechef ：

当且仅当所有字符出现在字符串中的次数相等时，才认为该字符串是 balanced 。

为您提供字符串 S ；该字符串只能包含大写英文字母。您可以多次执行以下操作（包括零次）：在 S 中选择一个字母，然后将其替换为另一个大写英文字母。请注意，即使替换的字母多次出现在 S 中，也只会替换该字母的所选出现。

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.

示例：

输入： ABCB

在这里，我们可以替换 C A ，得到： ABAB ，其中字符串的每个字符出现两次。

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

因此，最小操作数= 1 。

So, the number of minimum operation(s)=1.

如何使字符串变好？

我可以对其应用动态编程吗？

Can I apply dynamic programming to it ?

推荐答案

我认为您在这里确实不需要动态编程。

I don't think you really need dynamic programming here.

O （length（ S ））时间：

One approach in O(length(S)) time:

• 迭代 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 。
  
  
  • Iterate over S, build a frequency-map (a mapping from distinct letters A–Z to counts). For your ABCB example, that would be A->1 B->2 C->1 D->0 E->0 ... Z->0, which we can represent as the array [1, 2, 1, 0, 0, ..., 0].
    • We can do this because we don't actually care about the positions of letters at all; there's no real difference between ABCB and ABBC, in that each can be balanced by replacing their C with an A.
    
    
    • 我们可以这样做是因为我们实际上并不关心哪个字母是哪个字母； ABCB 和 ABDB 之间没有真正的区别，因为可以通过将每个单字母替换为
    
    
    • We can do this because we don't actually care about which letter was which; there's no real difference between ABCB and ABDB, in that each can be balanced by replacing one of their singleton letters with their other one.
    
    
    • 首先，检查length（ S ）是 i 的倍数；如果不是，则不可能，因此跳到下一个整数。
    
    
    • 接下来，计算 ^{length（ S ）} / < sub> i ，即最终平衡字符串中每个不同字母的计数。
    
    
    • 要计算需要执行的操作数，我们将检查所有计数需要增加。 （我们可以等效地检查需要减少的计数：它们必须匹配。）
    
    
    • 我们只对最后一个<排序数组中的em> i 元素。该点之前的任何元素都表示不会在平衡字符串中出现的字母：或者计数已经为零并将保持不变，或者为非零但将减小为零。无论哪种方式，由于我们仅跟踪增加，因此我们可以忽略它们。
    
    
    • 对于每个最近的 i 个计数，小于 ^{length（ S ）} / _i ，将其相加。该总和是操作数。 （请注意，由于对计数进行了排序，因此当您得到的计数大于或等于目标计数时，您可以立即退出此内部循环。）
    
    
    • 您可以退出此循环在第一个 i 之后循环，第一个 i 大于或等于原始 S 中不同字母的数量（除了我们拥有的 i 的值跳过，因为它们没有平均分割长度（ S ））。例如，如果length（ S ）  =  100，并且原始的 S 具有19个不同的字母，那么我们只需要考虑 i 最高为20。（提示 Eric Wang 的建议）。
    
    
    • First, check that length(S) is a multiple of i; if not, this isn't possible, so skip to the next integer.
    • Next, compute ^length(S)/_i, the count of each distinct letter in the final balanced string.
    • To count how many operations need to be performed, we're going to examine all the counts that need to be increased. (We could, equivalently, examine the counts that need to be decreased: they'll have to match.)
    • We're only interested in the last i elements of the sorted array. Any elements before that point represent letters that won't occur in the balanced string: either the counts are already zero and will remain so, or they are nonzero but will be decreased to zero. Either way, since we're only tracking increases, we can ignore them.
    • For each of the last i counts that are less than ^length(S)/_i, add the difference. This sum is the number of operations. (Note that, since the counts are sorted, you can exit this inner loop as soon as you get to a count that's greater than or equal to the target count.)
    • You can exit this loop after the first i that's greater than or equal to the number of distinct letters in the original S (aside from values of i that we had to skip because they don't evenly divide length(S)). For example, if length(S) = 100, and the original S has 19 distinct letters, then we only need to consider i as high as 20. (Hat-tip to Eric Wang for suggesting something along these lines.)

    这篇关于如何找到使字符串平衡的最小操作数？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！