497/670

497. Reorganize String

Medium

You are given a string s of lowercase letters. Shuffle its characters into a new order so that no two identical letters sit next to each other. Every character of s must be used exactly once — the result is a rearrangement, not a subsequence.

Usually many orderings qualify, so the answer is pinned down: return the lexicographically smallest valid rearrangement. If no valid rearrangement exists at all, return the empty string.

For example, "aab" can become "aba" (the only valid ordering), while "aaab" is hopeless — three as cannot avoid touching in four slots — so its answer is "".

Example 1:

Input: s = "aab"

Output: "aba"

Explanation: The three orderings that separate the two a's boil down to "aba" — b must sit between them. It is trivially the smallest valid answer.

Example 2:

Input: s = "aaab"

Output: ""

Explanation: Three a's in a string of length 4 would need to occupy alternating slots, but there are only two such slots on each parity — some pair of a's must touch. No valid rearrangement exists, so the answer is the empty string.

Constraints:

1 ≤ s.length ≤ 500
s consists of lowercase English letters only.

Hints:

First settle existence: if some letter has more than ceil(n / 2) copies, every arrangement forces two of them together (pigeonhole over alternating slots), so the answer is "". Otherwise a valid arrangement always exists.

Lexicographically smallest means: at each position try letters a → z and commit to the first that works. But "has copies left and differs from the previous letter" is not enough — placing it must leave a completable remainder.

After tentatively placing letter c with r characters still to lay down, the remainder is completable (with c banned from the very next slot) iff its highest count is <= ceil(r / 2) and not (r is odd and c itself still holds ceil(r / 2) copies). That test is O(26), and each slot tries at most 26 letters, giving an O(26² · n) sweep — effectively linear.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

Input: s = "aab"

Expected output: "aba"