Reorganize String
Problem
s so that no two
neighbouring characters are equal. Return any arrangement that works, or the empty string
"" if no such arrangement exists.s = "aab"Output"aba"s = "aaab"Output""s = "aaabbc"Output"ababac" (any valid answer accepted)1 ≤ s.length ≤ 500 · s consists of lowercase English letters
Try it yourself
class Solution {
public String reorganizeString(String s) {
}
}
⌈n/2⌉; then dropping it on indices 0, 2, 4, … and
filling the remaining slots with the other letters (evens first, then odds) never puts two
equal letters side by side.Instinct Need "have I seen this before?", "how many times?" or "group things that look alike"? Trade memory for O(1) lookups with a HashMap, HashSet or int[26].
Memory hack Don't search, remember - every element checks in at the front desk, and the desk answers instantly.
Open the Hashing & Counting guide →Approaches
Brute ForceBacktracking over Letter Counts
O(kn)Space O(n)Build the answer position by position. At each position try every letter that still
has copies left and differs from the previous letter; recurse, and undo the choice if the
rest cannot be completed. k = distinct letters (≤ 26).
public String reorganizeString(String s) { int[] left = new int[26]; for (char c : s.toCharArray()) left[c - 'a']++; char[] out = new char[s.length()]; return place(left, out, 0) ? new String(out) : ""; } private boolean place(int[] left, char[] out, int pos) { if (pos == out.length) return true; for (int c = 0; c < 26; c++) { if (left[c] == 0 || (pos > 0 && out[pos - 1] == 'a' + c)) continue; left[c]--; out[pos] = (char) ('a' + c); if (place(left, out, pos + 1)) return true; left[c]++; // undo and try the next letter } return false; }
Explores the arrangement space blindly — exponential on bad inputs.
BetterMax-Heap Greedy with Cool-Down
O(n log k)Space O(k)Always emit the letter with the most copies remaining, because it is the one most likely to get stuck later. The letter just used is held out of the heap for one step, so it can never be chosen twice in a row. If the heap empties early, it is impossible.
public String reorganizeString(String s) { int[] count = new int[26]; for (char c : s.toCharArray()) count[c - 'a']++; // entries are {letter, remaining}; most remaining first PriorityQueue<int[]> heap = new PriorityQueue<>((x, y) -> y[1] - x[1]); for (int c = 0; c < 26; c++) { if (count[c] > 0) heap.add(new int[]{c, count[c]}); } StringBuilder sb = new StringBuilder(); int[] cooling = null; // the letter used in the previous step while (!heap.isEmpty()) { int[] cur = heap.poll(); sb.append((char) ('a' + cur[0])); cur[1]--; if (cooling != null && cooling[1] > 0) heap.add(cooling); cooling = cur; } return sb.length() == s.length() ? sb.toString() : ""; }
Intuitive greedy that generalises (e.g. distance-k rearrangement), with a heap's log factor.
OptimalEven-Then-Odd Slot Filling
O(n)Space O(1)Count letters and find the most frequent one. If it exceeds
(n+1)/2, return "". Otherwise place it on even indices first,
then continue filling even indices with the other letters and wrap to index 1 when they
run out. Copies of one letter land two apart, so neighbours always differ.
public String reorganizeString(String s) { int n = s.length(); int[] count = new int[26]; for (char c : s.toCharArray()) count[c - 'a']++; int top = 0; for (int c = 1; c < 26; c++) { if (count[c] > count[top]) top = c; } if (count[top] > (n + 1) / 2) return ""; char[] out = new char[n]; int idx = 0; while (count[top] > 0) { // most frequent letter on 0, 2, 4, ... out[idx] = (char) ('a' + top); idx += 2; count[top]--; } for (int c = 0; c < 26; c++) { while (count[c] > 0) { if (idx >= n) idx = 1; // evens are full: switch to odds out[idx] = (char) ('a' + c); idx += 2; count[c]--; } } return new String(out); }
Dry runs = "aab"
- check······max a=3 ≤ (6+1)/2
- aax·ax·ax·evens 0,2,4
- babxa·a·idx 6 ≥ n → 1
- bababxa·idx=3
- cababacxababac ✔
Linear time with a 26-slot table and a direct feasibility test.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Backtracking over Letter Counts | O(kn) | O(n) |
| Better | Max-Heap Greedy with Cool-Down | O(n log k) | O(k) |
| Optimal | Even-Then-Odd Slot Filling | O(n) | O(1) |
- Using
n/2instead of(n+1)/2— rejects valid odd-length inputs like "aba". - Popping the top two from a heap at once without a cool-down — ties can produce "abba".
- Filling odd slots before the dominant letter has taken its evens.
- State the feasibility condition first: max count ≤ ⌈n/2⌉.
- Ask whether any valid answer is accepted — it is, so greedy is fine.
- Mention the heap version extends to Rearrange String k Distance Apart.