Skip to main content
Back to ChallengesReorganize StringHard 50 min

Reorganize String

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.

Examples

Input: s = 'aab'
Output: 'aba'
Rearranged so 'a's aren't together.
Input: s = 'aaab'
Output: ''
Impossible to separate three 'a's with one 'b'.

Constraints

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

Complexity Analysis

Time
O(N)
character frequencies and filling the array.
Space
O(1)
since alphabet is 26 characters max.

Test Cases

#1 Possible
Input: s = 'aab'
Expected: 'aba'
#2 Impossible
Input: s = 'aaab'
Expected: ''
Output
Click "Run Code" to see output here...