algorithm - How to find the minimum number of operation(s) to make the string balanced?

Question

From 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.

How to make the string good?

Can I apply dynamic programming to it ?

Answer 1

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

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

• 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 its C with an A.
• Sort the array. For your example, that gives [0, 0, ..., 0, 1, 1, 2].
  • 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 its singleton letters with its other one.
• Assuming the string is nonempty (since if it's empty then the answer is just 0), the final balanced string will contain at least 1 and at most 26 distinct letters. For each integer i between 1 and 26, determine how many operations you'd need to perform in order to produce a balanced string with i distinct letters:
  • 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.)
• Return the least of these up-to-26 sums. (Note that you don't actually need to store all the sums; you can just keep track of the minimum.)