If all characters were distinct, we could put them in any order and it works. For two instances of a repeated character, we need to put a different character in-between.
The best choice to put in-between two instances of the most frequent character is the second most frequent character. Because, in that way we would be leaving less frequent characters which might not require any interleaving.
Say len(s) = 
Time: 
from heapq import heapify, heappush as push, heappop as pop
class Solution:
def reorganizeString(self, s: str) -> str:
count_of = {}
for c in s:
if c not in count_of:
count_of[c] = 1
else:
count_of[c] += 1
max_heap = [(-count, char) for char, count in count_of.items()]
heapify(max_heap)
reorg = []
while max_heap:
neg_count, most = pop(max_heap)
most_count = -neg_count
if not max_heap:
if most_count > 1:
return ""
else:
reorg.append(most)
break
neg_count, second_most = pop(max_heap)
second_most_count = -neg_count
reorg.extend([most, second_most])
reduced_count = most_count-1
if reduced_count > 0:
push(max_heap, (-reduced_count, most))
reduced_count = second_most_count-1
if reduced_count > 0:
push(max_heap, (-reduced_count, second_most))
return "".join(reorg)
unreasonably effective 
Leave a comment