Reorganize String
Medium Max-heap, place two at a time
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Rearrange the letters of a string so no two adjacent letters are equal. Return any valid result, or "" if impossible.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: rearrange so no two neighbours are the same letter.
Why this works: always place the two most frequent remaining letters together; it's impossible if one letter has more than (n + 1) / 2.
Example: "aaabc"
take a, b → "ab", then a, c → "abac", then a → "abaca"✦Hints open one at a time
↗Approach
Max-heap of (letter, count). Repeatedly poll the top two letters, append both, decrement and push back the ones still left. If one letter remains at the end, append it (its count must be 1).
</>Solution (Java)
import java.util.*;
class Solution {
public String reorganizeString(String s) {
int[] count = new int[26];
for (char c : s.toCharArray()) count[c - 'a']++;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> b[1] - a[1]); // {letter, count}
for (int i = 0; i < 26; i++) {
if (count[i] > (s.length() + 1) / 2) return "";
if (count[i] > 0) heap.offer(new int[]{i, count[i]});
}
StringBuilder sb = new StringBuilder();
while (heap.size() >= 2) {
int[] a = heap.poll(), b = heap.poll(); // two different letters
sb.append((char) ('a' + a[0])).append((char) ('a' + b[0]));
if (--a[1] > 0) heap.offer(a);
if (--b[1] > 0) heap.offer(b);
}
if (!heap.isEmpty()) sb.append((char) ('a' + heap.poll()[0]));
return sb.toString();
}
}!Common mistake
Polling one letter at a time without holding it back — you may place the same letter twice in a row.
- Time: O(n log 26) = O(n).
- Space: O(26).