A label printer smudges whenever it prints the same letter twice in a row. Given a string, reorder its letters so that no two adjacent characters are equal.
Write rearrange(s) -> str that returns any reordering of s (using every letter exactly as many times as it appears) in which no two neighbouring characters are the same. If no such reordering exists, return the empty string "".
Any valid answer is accepted.
rearrange("aab") # "aba"
rearrange("aaab") # "" (three a's can't be kept apart by one b)
rearrange("aabbcc") # "abcabc" (or "cbacba", "abacbc", ...)
rearrange("z") # "z"
Constraints:
1 <= len(s) <= 2 * 10^5;scontains only lowercase English letters.- Trying orderings one by one is hopeless. Aim for O(n log k), where
kis the number of distinct letters (at most 26).
Show hint
Greedily place the letter with the most copies still unplaced, as long as it differs from the one you just placed. Keep the counts somewhere that always hands you the largest, and hold the letter you just used back for one step.