Reorganize String - Priority Queue / Heap / Moving Best

Problems
24

Here’s my solution in Python using the Counter class. I build a valid string by drawing from the unique letters of the input string, one of each kind at a time, until the counter class is either all zeros (the input is even and I used all letters), or only the most frequent letter remains. If there is only one of the latter, I can add it to the end of the new string and we are good to go. However, if there is more than one remaining “highest-frequency” letter, then I am forced to create a duplicate string.

Building the counter at the top is O(n). The while loop might run up to k times, where k is the frequency of the most common letter. Therefore the time complexity of the while loop is k*something, where something is the complexity of what happens inside the loop. Since each line inside the loop is no worse than O(n) then the loop itself is O(n) (dropping some constant). Time complexity overall is then O(n) + kO(n) or simply O(n).

from typing import Counter

def reorganize_string(s: str) -> str:
    # WRITE YOUR BRILLIANT CODE HERE

    counts = Counter(s)
    res = []
    while len(counts) > 1: # loop to draw all letters from the counter
        letters = list(counts) # we could do this only when len(counts) changes
        res.append(''.join(letters))
        counts.subtract(letters) # decrease counts by one
        counts += Counter() # remove zero-count entries

    res = ''.join(res + list(counts))
    
    # algomoster's Python doesn't like 'counts.total()' :-(
    # return '' if counts.total() > 1 else res
    
    # hack for algomonster's python
    if not counts:
        return res
    most_common = counts.most_common(1)[0]
    most_common_letter = most_common[0]
    remaining_count = most_common[1]
    return '' if remaining_count > 1 else res
25

Sorry, but this is not the correct solution unless I don’t understand part of the description “If possible, output any possible result”. To me, it’s all about permutations. This should be clarified or moved to a suitable section with permutations.

26

Because it needs to start with most common character, otherwise there is a chance that characters are filled adjacent to each other.
And heapify takes only O(n) time is better than build-in sort O(NlogN)?

27

actually, you don’t, the simplest way is just iterating all letters repeatedly and picking one at a time, if a letter you picked is the same as the immediate previous one, then you know you can’t form a string.

using a priority queue is a different way of placing the letters.

28

You don’t need heappop. The solution can be O(N), which doesn’t make a difference if k is small, but k can be large. The original heap order can be repeated, decrementing counts and skipping chars with count=0. For instance:
pq=[(-5,'a'),(-3,'b'),(-2,'c')], you would do abcabcababa.