Re-arrange a string so that no two adjacent elements are the same character

[darwinrlo]

LeetCode: Reorganize String

[darwinrlo]

For each unique character, there needs to be enough occurrences of other characters in the string to separate them.

If there are enough occurrences of other characters to separate occurrences of the most frequently occurring characters, then this is certain true for other characters. What's left is to figure out if there is a configuration in which the unique characters are mutually separating.

[darwinrlo]

Example:

• There are two occurrences of the letter a.
• There is one occurrence of the letters b through g.

aabcdefg

The greatest character count is 2. Besides the most frequently occurring character, there are 6 occurrences of other characters. There are not enough occurrences of the most frequent character to separate the other characters -- but there are enough of them to separate each other out.

But there are enough occurrences of other letters to separate occurrences of the most frequent character. In general, for each unique character, there must be enough occurrences of other characters to separate occurrences of the aforesaid unique character.

[darwinrlo]

Suppose we have a string of length n that meets the target property; that is, in the string, no two adjacent positions are occupied by like characters.

Now, say we are given n+1 instances of a new character. Is it possible to construct a new string containing all of the elements of the original string as well as the new elements?

Yes. There are enough characters in the original string to separate all n+1 instances of the new character from each other. To construct such a string, start with an instance of the new element, and alternate between a character from the old string and an instance of the new character. The last character of the new string will be an instance of the new character and we'll have a property-meeting string.

If we were given fewer than n+1 instances, it'd be an even easier problem, so we would also be able to construct a property-meeting string in those cases. If there were n+2 instances or more though, there would not be enough other characters to separate them.

[darwinrlo]

Claim: If all unique characters occur equally frequently in a string, then there exists a target-property-meeting re-arrangement.

If the number of unique characters is 1, there is no possible re-arrangement that would meet the target property.

If the number of unique characters is 2, then a re-arrangement can be constructed by alternating between instances of the two characters.

Let m be the number of occurrences of a unique character. As referenced previously, the number of occurrences of a given unique character from the string is m. Given a string with k unique characters, where k > 2, to construct a target-property-meeting re-arrangement:

• We can take the instances of two distinct characters from the original string and create a target-property-meeting string by alternating between instances of the two characters. Now, we have a string that meets the target property. It is of size 2m.
• We know that, if we have a target-property-meeting string of size n and are given n+1 or fewer instances of a new character, we can create a new string that also meets the target property. In this case, we can take our string and up to 2m+1 instances of a new character and create a new target-property-meeting string.
• Accordingly, since there are m instances of each of the remaining unique characters, we can create yet another target-property-meeting string from the instances of another character. This yields an even bigger string. And it gets even more clearly feasible to create a new target-property-meeting string with the instances of any of the remaining characters.
• We can repeat this until we have incorporated all instances of all unique characters to create a target-property-meeting re-arrangement of the original string.

Hence, if a string has two or more unique characters and they all occur with the same frequency, a target-property-meeting re-arrangement exists. QED.

[darwinrlo]

Heap-Based Solution

Summary

Insert the unique characters in a max-heap, keyed by the number of instances that still need to be added to the result string. On each loop iteration, extract the top element from the heap -- the character with the greatest number of remaining instances -- and add it to the result string. Decrement the number of remaining occurrences and keep it out of the heap until the end of the next loop iteration to prevent it from being added to the result string again on the next loop iteration.

Correctness

At any given time, the algorithm is switching off between at least two top characters. As the top characters get depleted, other characters come into the mix and the number of characters that the algorithm switches off between increases.

At some point, all the character counts reach 1 -- perhaps they were already one -- and the characters get completely depleted one-by-one.

More frequent elements get depleted faster at the beginning but the pace at which they get depleted slows down as they are depleted and more characters come into the mix.

[darwinrlo]

Is there a solution?

For each character, there must be enough instances of other characters to separate each instance of the aforesaid character. This means that, if a character occurs n times in a string, there needs to be at least n-1 instances of other characters. If this is not true for even a single character, there is no solution. This condition is necessary -- but not necessarily sufficient.

Interesting Case

• For each character, there are enough instances of other characters to separate each instance of the aforesaid character.
• Let the number of occurrences of the most frequent characters ー there might be more than one with the greatest frequency ー be n. There are more than n+1 instances of the other characters so there are not enough instances of the most frequent characters to separate them.

Under what circumstances is there a solution?

aaabbbccddeeff aaaabbbbcccdddeee aaaabbbbccddeefff

ccddeefff => fcdefcdef

Observation

• The other characters max out at n-1 instances. This seems important.

• It feels to me that, the fewer characters there are, the less likely there is to be a solution.

Old

Let max_freq be the maximum frequency observed in the string for any character.

If there is one character with this frequency:

• If there are fewer than max_freq - 1 occurrences of other characters, then there are not enough other characters to separate the instances of the most frequent character. Return false.
• If there are max_freq - 1 to max_freq + 1 occurrences of other characters,
• More than max_freq + 1 other characters, there are enough instances of other characters to separate instances of the most frequent character... with some left over. There may or may not be a solution.

Which is greater, max_freq or the number of other characters?

• If max_freq is greater, there is a solution iff there are no fewer than max_freq - 1 occurrences of the other characters.
• If the number of other characters is greater, there are enough of them to separate occurrences of the most frequent character, but there are not enough of the most frequent character to separate occurrences of the other characters. There is a solution if say all the instances are distinct characters and no solution if all the other characters are the same.

If there are not enough of the most frequent characters to separate occurrences of the other characters, there is a solution if there is a solution for the other characters without the most frequent characters. If there's not, I don't know that there's not a solution.