Reorganize String

Medium· max-heap· greedy

Problem

Rearrange the letters of a string so that no two neighbouring characters are the same. Return any valid arrangement, or an empty string if it cannot be done.

Examples

Input: s = "aab"

Output: "aba"

Input: s = "aaab"

Output: ""

Three a's cannot be separated by a single b.

Constraints

• 1 <= s.length <= 500
• s has only lowercase English letters

Hints & approach

Hint 1

It is impossible exactly when some letter appears more than (n + 1) / 2 times.

Hint 2

Greedily place the most frequent letter that differs from the last placed one.

Hint 3

A max-heap of (count, letter) supports that greedy choice.

Approachtry the hints first

Count letters and push (count, letter) into a max-heap. Repeatedly pop the most frequent letter, append it, and decrement its count; hold it aside for one round instead of pushing it back immediately, so the next pick is forced to be a different letter. After the next pop, push the held letter back if it still has copies left. If the output length falls short of n, some letter could not be spaced out, so return "".

Time O(n log A), A = alphabet size · Space O(A)

← PreviousFind K Pairs with Smallest Sums Next →Find Median from Data Stream