Rearrange a string so no two adjacent characters are the same

Medium

Problem

Rearrange the characters of the string so that no two adjacent characters are equal. Return any valid arrangement, or "" if none exists.

Example 1

Input:  "aab"
Output: "aba"

Example 2

Input:  "aaab"
Output: ""

Three a’s cannot be separated by a single b.

Also asked as: Rearrange characters in a string such that no two adjacent are same · Leetcode- reorganize strings · reorganize strings

Test cases

Case 1

Input:    "aab"
Expected (any of): ["aba"]

Case 2

Input:    "aaab"
Expected (any of): [""]

Case 3

Input:    "aaabb"
Expected (any of): ["ababa"]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Greedy — always place the most frequent remaining char

Time O(n · k)Space O(k)

Repeatedly append the highest-count character that is not the one just placed. Impossible iff some char’s count exceeds ceil(n/2).

function reorganize(s) {
const freq = new Map();
for (const c of s) freq.set(c, (freq.get(c) || 0) + 1);
let res = '', prev = '';
for (let i = 0; i < s.length; i++) {
let best = '';
for (const [c, n] of freq) if (n > 0 && c !== prev && (best === '' || n > freq.get(best))) best = c;
if (best === '') return '';
res += best;
freq.set(best, freq.get(best) - 1);
prev = best;
}
return res;
}

With a real max-heap keyed by frequency this is O(n log k).