Consider a string s. Your task is to rearrange its characters so that no adjacent characters are the same. If that's possible, return any valid rearrangement. If not, return an empty string "". Amazon interviewers use greedy + heap problems to evaluate your priority-based scheduling instincts.
For example, given "aab", one valid answer is "aba". Given "aaab", no rearrangement works because 'a' appears times in a -character string, so you'd always end up with consecutive 'a's. Return "".
Before jumping to code, consider: when exactly is rearrangement impossible? What relationship between a character's frequency and the string length determines the answer?