230. Rearrange a String So That No Two Adjacent Characters Are the Same

Given a string s of lowercase English letters, rearrange its characters (using every character exactly once) so that no two adjacent characters are equal. Build the arrangement with this exact greedy procedure so the result is unambiguous: repeatedly place the character with the largest remaining count; if multiple characters are tied on remaining count, prefer the alphabetically smallest one; if the resulting top choice is the same character you just placed, temporarily set it aside and place the next-best character instead (returning the set-aside one to the pool for later). Print the final string, or print -1 if no valid arrangement exists.

Input: A single line containing the string s of lowercase English letters. Output: Print the rearranged string produced by the specified greedy procedure, or print -1 if no valid arrangement exists.

1 <= |s| <= 10^5, s consists of lowercase English letters

The problem's exact tie-breaking rule (alphabetically smallest among equally-frequent candidates) makes the output DETERMINISTIC and specific - without following this exact rule precisely, a technically-valid-but-differently-ordered answer would not match the expected output.

Rearrange a string's letters so no two neighboring letters are the same, following a specific greedy 'always place the most frequent remaining letter' rule. Brute force: Try every possible permutation of the string's characters directly and check which ones have no adjacent duplicates - this is exponential (factorial in the string's length), completely impractical beyond tiny strings. Optimised: A max-heap always keyed by REMAINING count naturally enforces the greedy 'always use up the most common remaining letter first' strategy, which is provably necessary to avoid getting stuck with too many of one letter near the end - the 'set aside and retry' step specifically handles the case where the greedy top choice would create an illegal adjacent duplicate.

Keep a count array for the 26 letters; at each step scan the counts to find the character with the largest remaining count that isn't the same as the character just placed (preferring alphabetically smallest on ties), place it, decrement its count, and repeat. Because the alphabet is fixed at 26 letters, each placement's scan is bounded by a constant, but that constant work is still redone from scratch at every single position instead of being maintained incrementally. Time: O(26n) Space: O(26)

Push all 26 (character, count) pairs into a max-heap keyed by count; repeatedly pop the top, and if it's the same character just placed, pop the next one instead and push the first one back for later, place the chosen character, decrement its count, and push it back if still positive. The heap maintains the frequency ordering incrementally in O(log 26) per operation instead of rescanning all counts from scratch on every placement, and the greedy choice (always placing the currently most frequent valid remaining character) is what guarantees a valid arrangement exists whenever one is possible (i.e. no letter's count exceeds ceil(n/2)). Time: O(n log 26) Space: O(26)

Recursively build the result character by character, at each position trying every one of the 26 letters that still has remaining count and isn't equal to the previously placed character, backtracking whenever a choice leads to a dead end later. This blindly searches the space of arrangements and can revisit the same failing structure many times before succeeding or exhausting all options. Time: O(26^n) worst case Space: O(n)

1. Count how many times each character appears. 2. Use a max-heap (priority queue) keyed by remaining count (breaking ties alphabetically), always popping the best candidate to place next. 3. If the just-popped candidate is the same character you JUST placed, temporarily set it aside, place the next-best candidate instead, then push the set-aside one back into the heap for a later turn. 4. Repeat until every character has been placed.

Time: O(n log k), where k is the number of distinct characters - each of the n characters placed requires an O(log k) heap operation. Space: O(k), for the max-heap holding at most one entry per distinct character.

Test with |s|=1 (trivially valid), a string where one character's count exceeds ceil(|s|/2) (impossible, print -1), a string of all-identical characters with length > 1 (also impossible), and |s|=10^5 to confirm heap-based performance.

Be ready to state the feasibility check explicitly: a valid arrangement exists if and only if the most frequent character's count doesn't exceed ceil(|s|/2) - checking this upfront quickly identifies impossible cases before attempting construction.