275. Reorganize a String So No Two Adjacent Characters Repeat

Given a string s of lowercase English letters, rearrange its characters so that no two characters that end up adjacent are equal, and print the result. If it's impossible, print -1. Multiple valid rearrangements can exist, so build the answer with this exact rule to make it unique: at every step, among the characters that still have letters remaining and aren't equal to the character you placed immediately before, place the one with the highest remaining count, breaking ties by the alphabetically smaller character.

Input: A single line contains the string s, consisting of lowercase English letters. Output: Print the rearranged string with no two adjacent characters equal, or print -1 if no valid rearrangement exists.

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

The EXACT tie-breaking rule specified (alphabetically smaller among equal-frequency candidates) makes the output fully deterministic - this is the same underlying technique as the closely-related 'Rearrange a String So That No Two Adjacent Characters Are the Same' problem from the Strings category.

Rearrange a string's letters so that no two adjacent characters are the same, using a specific greedy tie-breaking rule for a unique, deterministic answer. Brute force: Try every possible permutation of the string's characters and check which ones satisfy the no-adjacent-duplicates rule - this is exponential (factorial in the string's length), completely impractical. Optimised: A max-heap always keyed by (remaining count, then alphabetical tie-break) enforces the greedy 'always use up the most common remaining letter first' strategy necessary to avoid getting stuck with too many of one letter near the end - the 'set aside and retry' step specifically handles avoiding placing the same character twice in a row.

Build a max-heap keyed first by remaining character count (descending) and then by character value (ascending) to match the required tie-break rule exactly. Repeatedly pop the top of the heap; if it's the same character just placed, set it aside and pop the next one instead (holding the previous pick out of the heap for exactly one round so it isn't chosen twice in a row), place the chosen character, decrement its count, and push both the placed character (if count remains) and the held-back one back into the heap. If at some point the heap is empty but characters remain, it's impossible. Because the heap's comparator directly encodes 'highest remaining count, ties broken by smaller character,' this produces precisely the deterministic arrangement the problem asks for, in logarithmic time per character. Time: O(|s| log 26) Space: O(26)

Recursively try building the answer character by character: at each position, try placing any character that still has remaining count and isn't equal to the previously placed character, decrement its count, and recurse to the next position; if a full arrangement of length |s| is completed, it's a valid answer, otherwise backtrack and try a different character. This explores the space of arrangements directly and will find a valid one if it exists (or correctly report impossibility if none does), but the branching factor makes it exponential for longer strings. Time: O(26^|s|) (exponential) Space: O(|s|)

Count the frequency of each character, and if any character's frequency exceeds ceil(|s|/2), it's impossible to arrange without a repeat, so print -1 immediately. Otherwise, sort characters by descending frequency, and place them by filling all the even indices (0, 2, 4, ...) first, then all the odd indices (1, 3, 5, ...) - this spaces out the most frequent characters as much as possible. This produces some valid rearrangement in one pass after sorting, a huge improvement over backtracking, though it doesn't automatically follow the specific highest-remaining-count-with-alphabetical-tiebreak placement rule required to get the exact expected output. Time: O(|s| log |s|) Space: O(|s|)

1. Count each character's frequency; if any character's count exceeds ceil(n/2), no valid arrangement can EVER exist - print -1 immediately. 2. Use a max-heap keyed by (remaining count, then alphabetically-smaller character for ties) to always find the best next candidate in O(log 26) time. 3. If the heap's top character equals the one just placed, temporarily set it aside, use the next-best candidate instead, then push the set-aside one back in for a later turn.

Time: O(n log k), where k is the number of distinct characters (bounded by 26 for lowercase letters) - 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.

|s| = 1 (trivially valid), a string where some character's count exceeds ceil(n/2) (impossible, print -1), and |s| = 10^5 for heap performance.

Be ready to state the feasibility check explicitly (most frequent character's count must not exceed ceil(n/2)) and to justify it - if it did exceed this bound, there simply wouldn't be enough 'other' characters to separate all its occurrences.