Rearrange characters so no two adjacent chars are same. Return any valid arrangement or "".
Input: s="aab" → Output: "aba"
Input: s="aaab" → Output: "" (impossible)
Use a max-heap. Always pick the most frequent character that is different from the previous one.
- Count character frequencies
- Use max-heap (by frequency)
- Each step: poll most frequent (not same as last placed)
- If only one type left and it equals last, impossible
- Append character and offer back with decremented count
public String reorganizeString(String s) {
int[] freq = new int[26];
for (char c : s.toCharArray()) freq[c - 'a']++;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
for (int i = 0; i < 26; i++) if (freq[i] > 0) pq.offer(new int[]{i, freq[i]});
StringBuilder sb = new StringBuilder();
while (pq.size() >= 2) {
int[] a = pq.poll(), b = pq.poll();
sb.append((char)('a' + a[0]));
sb.append((char)('a' + b[0]));
if (--a[1] > 0) pq.offer(a);
if (--b[1] > 0) pq.offer(b);
}
if (!pq.isEmpty()) {
int[] last = pq.poll();
if (last[1] > 1) return "";
sb.append((char)('a' + last[0]));
}
return sb.toString();
}
- Time Complexity: O(n log k)
- Space Complexity: O(k)