Rearrange a string so no two adjacent characters are the same
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"]
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).