hardHeap / Priority QueuePure DSA~35 min
Rearrange a String So No Two Adjacent Chars Match
Reorder the characters of a string so that no two adjacent characters are the same, or report that it is impossible.
Problem
Given a string s, rearrange its characters so that no two adjacent characters are identical. Return any valid rearrangement, or an empty string if none exists.
Input
A string s of lowercase letters.
Output
A rearranged string, or an empty string if impossible.
Constraints
- 1 <= s.length <= 500
- s consists of lowercase English letters.
- Return any one valid answer.
Examples
Example 1
Input
s = "aab"
Output
"aba"
The two a's are separated by b.
Example 2
Input
s = "aaab"
Output
""
Too many a's to separate.