101
0/320
Loading content...
You are given a string s composed entirely of lowercase English letters. Your task is to rearrange the characters of the string such that no two identical characters appear next to each other in the resulting string.
If such a rearrangement is achievable, return any valid permutation of the string that satisfies this constraint. If it is impossible to rearrange the characters to meet this requirement, return an empty string "".
The core challenge lies in distributing characters with high frequency across the string in a way that prevents them from being adjacent. For a valid rearrangement to exist, no single character can appear more than half the length of the string (rounded up). If a character occurs too frequently, it becomes impossible to separate all its occurrences with other characters.
Consider a string of length n. If any character appears more than ⌈n/2⌉ times (ceiling of n/2), then by the pigeonhole principle, at least two occurrences of that character must be adjacent in any arrangement. This gives us a quick way to determine feasibility before attempting any rearrangement.
A greedy strategy works well here: always place the most frequent remaining character that differs from the previously placed character. This ensures we're continuously reducing the count of high-frequency characters while maintaining the separation constraint. Priority queues (max-heaps) are particularly effective for efficiently retrieving the most frequent character at each step.
s = "aab""aba"The character 'a' appears twice and 'b' appears once. By placing 'a', then 'b', then 'a', we achieve "aba" where no two adjacent characters are the same. Other valid outputs like "aba" are also acceptable.
s = "aaab"""The character 'a' appears 3 times in a string of length 4. Since 3 > ⌈4/2⌉ = 2, it is impossible to arrange the characters such that no two 'a's are adjacent. Therefore, we return an empty string.
s = "aabb""abab"Both 'a' and 'b' appear twice. We can interleave them to get "abab" or "baba", both of which are valid solutions. The key is that each character count (2) does not exceed ⌈4/2⌉ = 2, making a valid arrangement possible.
Constraints