Reorganize String
Medium · Heap & Counting · Hash Table · String · Greedy · Sorting · Heap (Priority Queue) · Counting
Problem
Given a string s, rearrange its characters so that no two adjacent characters are the same.
Return any such rearrangement, or the empty string "" if none exists. Any valid rearrangement is accepted.
Examples
Input: s = "aaabc" Output: "abaca"
The three a’s take every other slot, which separates them; other valid answers such as "acaba" are also accepted.
Input: s = "zzzy" Output: ""
Three z’s need at least two separators, but only one other letter exists.
Input: s = "aab" Output: "aba"
The b goes between the two a’s; this is the only valid answer.
Constraints
- 1 <= len(s) <= 500
- s consists of lowercase English letters
Approaches
- Most frequent letter that differs from the last, scanning counts — time O(n · σ), space O(σ)
Follow-up
What if equal letters must be at least k positions apart instead of just not adjacent? Then every letter needs a cooling period: keep a max-heap of letters by remaining count and a queue of letters that were used in the last k - 1 positions. At each position take the most frequent letter not cooling; if none is available while letters remain, the answer is "".
Related problems
Start free on Cariara · Coding problems · System design studio
