Reorganize String

Medium

LeetCode ↗

Strings Hash Tables Heap Heap / Priority Queue Greedy

Problem

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

Constraints

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

Examples

Input: s = "aab"

Output: "aba"

We can rearrange 'aab' to 'aba' where no two adjacent characters are the same.

Input: s = "aaab"

Output: ""

There are 3 'a's but only 1 'b'. Even with optimal placement, we cannot avoid adjacent 'a's: 'a_a_a' needs at least 2 other characters to separate them.

Loading...

Loading Python...