Reorganize String

The key idea

A rearrangement exists only when the most frequent letter appears at most (n + 1) / 2 times. When it does, always placing the letter with the highest remaining count that differs from the last placed letter keeps the two copies apart.

Problem

Given a string s, rearrange its characters so that no two adjacent characters are the same.

Return any valid rearrangement. If no such rearrangement is possible, return the empty string "".

The answer is judged as correct as long as adjacent characters differ; when several rearrangements are valid, returning any one of them is accepted.

Constraints

1 <= s.length <= 500
s consists of lowercase English letters.

Examples

Input: s = "aab" Output: "aba"

Input: s = "aaab" Output: ""

Input: s = "aabbcc" Output: "abcabc"

Complexity

Time: O(n log k) Space: O(k)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →