Approach #1: Sort by Count [Accepted]
If we should make no two
'a's adjacent, it is natural to write
"X" is some letter. For now, let's assume that the task is possible (ie. the answer is not
Let's sort the string
S, so all of the same kind of letter occur in continuous blocks. Then when writing in the following interleaving pattern, like
S, S, S, S, S, S, adjacent letters never touch. (The specific interleaving pattern is that we start writing at index 1 and step by 2; then start from index 0 and step by 2.)
The exception to this rule is if
N is odd, and then when interleaving like
S, S, S, S, S, we might fail incorrectly if there is a block of the same 3 letters starting at
S. To prevent failing erroneously in this case, we need to make sure that the most common letters all occur at the end.
Finally, it is easy to see that if
N is the length of the string, and the count of some letter is greater than
(N+1) / 2, the task is impossible.
Find the count of each character, and use it to sort the string by count.
If at some point the number of occurrences of some character is greater than
(N + 1) / 2, the task is impossible.
Otherwise, interleave the characters in the order described above.
Time Complexity: , where is the length of , and is the size of the alphabet. In Java, our implementation is . If is fixed, this complexity is .
Space Complexity: . In Java, our implementation is .
Approach #2: Greedy with Heap [Accepted]
One consequence of the reasoning in Approach #1, is that a greedy approach that tries to write the most common letter (that isn't the same as the previous letter written) will work.
The reason is that the task is only impossible if the frequency of a letter exceeds
(N+1) / 2. Writing the most common letter followed by the second most common letter keeps this invariant.
A heap is a natural structure to repeatedly return the current top 2 letters with the largest remaining counts.
We store a heap of (count, letter). [In Python, our implementation stores negative counts.]
We pop the top two elements from the heap (representing different letters with positive remaining count), and then write the most frequent one that isn't the same as the most recent one written. After, we push the correct counts back onto the heap.
Actually, we don't even need to keep track of the most recent one written. If it is possible to organize the string, the letter written second can never be written first in the very next writing.
At the end, we might have one element still on the heap, which must have a count of one. If we do, we'll add that to the answer too.
Proof of Invariant
The invariant mentioned in the [Intuition] section seems true when playing with it, but here is a proof. Let be the count of each letter yet to be written, and be the number of letters left to write. We want to show this procedure maintains the invariant .
Say are the counts after one writing step.
If , then , and so as desired.
If , then . Also, because , . Then, as desired.
This completes the proof of this invariant.
Time Complexity: , where is the length of , and is the size of the alphabet. If is fixed, this complexity is .
Space Complexity: . If is fixed, this complexity is .
Analysis written by: @awice.