Given string s, rearrange its characters so that no two adjacent characters are the same. Return the rearranged string, or "" if impossible.
Input: "aab" → Output: "aba"Input: "aaab" → Output: ""
Use a max-heap. Always pick the most frequent character that differs from the previous one. If most frequent equals previous, use second most frequent.
- Count frequencies. Build max-heap of (freq, char) pairs.
- While heap non-empty: pop max-freq char.
- If it equals previous char: pop second, place it, push first back.
- Else place first, push second back if freq > 0.
- If heap has single element with freq > 1 and no prev different: return "".
import java.util.*;
class Solution {
public String reorganizeString(String s) {
int[] freq = new int[26];
for (char c : s.toCharArray()) freq[c-'a']++;
PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a,b)->b[0]-a[0]);
for (int i = 0; i < 26; i++) if (freq[i] > 0) maxHeap.offer(new int[]{freq[i], i});
StringBuilder sb = new StringBuilder();
while (maxHeap.size() >= 2) {
int[] first = maxHeap.poll(), second = maxHeap.poll();
sb.append((char)('a'+first[1])); sb.append((char)('a'+second[1]));
if (--first[0] > 0) maxHeap.offer(first);
if (--second[0] > 0) maxHeap.offer(second);
}
if (!maxHeap.isEmpty()) {
int[] last = maxHeap.poll();
if (last[0] > 1) return "";
sb.append((char)('a'+last[1]));
}
return sb.toString();
}
}
- Time Complexity: O(N log 26) = O(N)
- Space Complexity: O(26) = O(1)