Reorganize String: Spacing Out the Character That Dominates
Rearrange a string so no two adjacent characters match, using a frequency count and greedy even-then-odd placement — walkthrough, JavaScript code, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Reorganize String looks like a puzzle about shuffling letters, but it's really a question about one number: how often does the most common character appear? Get that count under control and the rest of the string falls into place almost mechanically.
The trap is reaching for backtracking — trying arrangements, hitting a conflict, and undoing. That works, but it's exponential and completely unnecessary. The character that shows up most is the only thing that can ever break, so the whole problem reduces to giving that character enough breathing room.
Once you see it that way, a single pass with a frequency map and a clever index step solves it in linear time.
The problem
Given a string s, rearrange its characters so that no two adjacent characters are the same. Return any valid arrangement, or an empty string "" if none exists.
Input: s = "vvvlo"
Output: "vlvov" // no two neighbors match
Input: s = "aaab"
Output: "" // three a's can't be separated in 4 slotsTwo facts drive everything:
- You only need to return one valid arrangement, not all of them — so a greedy construction is fair game.
- Feasibility hinges entirely on the most frequent character. If it appears too many times, no reshuffling saves you.
The brute force baseline
The naive instinct is to generate arrangements and check each one. A backtracking version places characters one slot at a time, skipping any choice that repeats the previous character, and backs up when it gets stuck.
function reorganizeStringBrute(s) {
const chars = s.split("");
const used = new Array(chars.length).fill(false);
const path = [];
function backtrack() {
if (path.length === chars.length) return path.join("");
for (let i = 0; i < chars.length; i++) {
if (used[i]) continue;
if (path.length && path[path.length - 1] === chars[i]) continue;
used[i] = true;
path.push(chars[i]);
const result = backtrack();
if (result) return result;
path.pop();
used[i] = false;
}
return "";
}
return backtrack();
}It's correct, but it explores a permutation tree. In the worst case — think a string of mostly unique characters — it approaches O(n!) work. On even a 12-character input that's already hundreds of millions of branches. The search never learns the one thing that actually decides the answer.
The key insight
Ask the pigeonhole question first. You have n positions. If you want to keep a character off its own neighbors, the tightest you can pack it is every other slot: indices 0, 2, 4, and so on. That gives exactly ceil(n / 2) non-adjacent slots.
So if the most frequent character appears more than ceil(n / 2) times, there literally aren't enough gaps — two copies must end up side by side, and the answer is "". That single comparison decides feasibility before you place anything. (In code, ceil(n / 2) is written as Math.floor((n + 1) / 2).)
When it is feasible, the construction is greedy: place the most frequent character first, into the even indices, then keep filling. Spreading the dominant character across every-other slot guarantees it can never touch itself. Fill even indices 0, 2, 4, …; the moment you run past the end, wrap to idx = 1 and continue down the odd indices 1, 3, 5, …. Because you handled the heaviest character while the most room was available, everything lighter slots into the leftover gaps without conflict.
The optimal solution
This mirrors the visualizer's algorithm: count, feasibility-check, sort unique characters by frequency descending, then place with the even-then-odd index step.
function reorganizeString(s) {
let freq = new Map();
let maxFreq = 0;
for (let char of s) {
freq.set(char, (freq.get(char) || 0) + 1);
maxFreq = Math.max(maxFreq, freq.get(char));
}
// Pigeonhole feasibility check
if (maxFreq > Math.floor((s.length + 1) / 2)) return "";
// Heaviest character first
let sorted = [...freq.keys()].sort((a, b) => freq.get(b) - freq.get(a));
let res = new Array(s.length);
let idx = 0;
for (let char of sorted) {
let count = freq.get(char);
while (count > 0) {
res[idx] = char;
idx += 2;
if (idx >= s.length) idx = 1; // wrap to odd indices
count--;
}
}
return res.join("");
}The idx += 2 with the idx >= s.length → idx = 1 wrap is the whole trick. It walks every even slot, then every odd slot, laying characters down in a fixed pattern that keeps identical letters two positions apart. Sorting descending guarantees the character most likely to collide gets first pick of the widely-spaced even indices.
Walkthrough
Trace s = "vvvlo". Counting gives v: 3, l: 1, o: 1, so maxFreq = 3. With n = 5, maxAllowed = floor(6 / 2) = 3, and 3 <= 3 — feasible. Sorted descending: ["v", "l", "o"]. Start idx = 0, res = [_, _, _, _, _].
| Char | count left | idx (write) | res after write | next idx |
|---|---|---|---|---|
| v | 3 | 0 | [v, _, _, _, _] | 2 |
| v | 2 | 2 | [v, _, v, _, _] | 4 |
| v | 1 | 4 | [v, _, v, _, v] | 6 → wrap to 1 |
| l | 1 | 1 | [v, l, v, _, v] | 3 |
| o | 1 | 3 | [v, l, v, o, v] | 5 → wrap to 1 |
Result: "vlvov". The three v's landed on 0, 2, 4 — never adjacent — and l, o filled the odd gaps. Watch the wrap: after writing the last v at index 4, idx jumps past the end and resets to 1, seamlessly switching from even to odd placement without any special-case code.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Backtracking brute force | O(n!) | O(n) | explores a permutation tree of arrangements |
| Greedy count + place | O(n + k log k) | O(n) | one pass to count, sort of k unique chars, one pass to place |
Here k is the alphabet size (at most 26 for lowercase letters), so k log k is effectively constant and the whole thing runs in O(n) practical time. Space is the frequency map plus the n-length result array.
Common mistakes
- Sorting the whole string instead of unique characters. You only sort the
kdistinct characters by frequency — sorting allncharacters is both wrong for placement and slower. - Using the wrong feasibility bound. The limit is
ceil(n / 2), writtenMath.floor((n + 1) / 2). Usingn / 2rejects valid odd-length inputs like"aab". - Forgetting the even-to-odd wrap. If you only fill even indices and stop, you overflow the array or leave odd slots empty. The
idx >= n → idx = 1reset is mandatory. - Not placing the heaviest character first. Skip the descending sort and a lighter character can grab a spread-out slot the dominant one needed, forcing a collision later.
- Returning early inside the placement loop. The empty-string case is decided before placement by the pigeonhole check — once you start placing, a valid result is guaranteed.
Where this pattern shows up next
Frequency counting plus greedy string construction powers a whole family of problems:
- Reverse Words in a String — another rearrange-in-place string problem where the order of operations is everything.
- Sum of Beauty of All Substrings — leans on the same max/min frequency bookkeeping over character counts.
- Decode String — building an output string by construction rather than search.
- Count and Say — run-length frequency counting that generates the next string from the last.
You can also step through Reorganize String interactively to watch the frequency map fill, the pigeonhole bar compare against the limit, and each character snap into its even-then-odd slot.
FAQ
When is it impossible to reorganize a string?
When the most frequent character appears more than ceil(n / 2) times, where n is the string length. With n positions, a character can occupy at most every other slot — ceil(n / 2) non-adjacent positions. Exceed that and the pigeonhole principle forces two copies to be adjacent no matter how you arrange the rest, so the answer is the empty string. For example, "aaab" has three a's but only ceil(4 / 2) = 2 non-adjacent slots, so it's impossible.
Why place the most frequent character first?
The dominant character is the only one at real risk of colliding with itself, and it needs the widely-spaced slots. Placing it first, into the even indices, guarantees maximum spacing before anything else competes for those positions. If you placed lighter characters first, they might occupy even slots the heavy character needed, squeezing it into adjacent positions and creating a conflict that a smarter order would have avoided.
What is the time complexity of the greedy solution?
O(n + k log k), where n is the string length and k is the number of distinct characters. Counting frequencies is one O(n) pass, sorting the k unique characters by count is O(k log k), and placing every character is another O(n) pass. Since k is bounded by the alphabet size (26 for lowercase letters), the sort is effectively constant, so the solution runs in linear O(n) time with O(n) space.
Does the even-then-odd placement always avoid adjacent duplicates?
Yes, as long as the feasibility check passed. By filling even indices first with characters sorted by descending frequency, then wrapping to odd indices, identical characters are always placed at least two positions apart — the write index advances by 2 every time. The wrap to index 1 only happens after the even slots are exhausted, and because no character exceeds ceil(n / 2) occurrences, none of them ever runs long enough to wrap back onto its own even-index copy.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.