Practice/Amazon/Leetcode 767. Reorganize String

Leetcode 767. Reorganize String

CodingMust

Problem

Given a string containing lowercase letters, rearrange its characters so that no two adjacent characters in the result are identical. If multiple valid arrangements exist, return any one of them. If no valid arrangement is possible, return an empty string.

Your task is to determine whether such a rearrangement exists and construct one if possible.

Requirements

1. Return any valid string where no two adjacent characters are the same
2. If no valid arrangement exists, return an empty string ""
3. The output must contain exactly the same characters as the input (same frequencies)
4. If multiple solutions exist, any valid solution is acceptable

Constraints

• 1 ≤ s.length ≤ 500
• s contains only lowercase English letters
• Time complexity should be O(n log k) where n is string length and k is number of unique characters
• Space complexity should be O(k) for storing character frequencies

Examples

Example 1:

Input: s = "aabbcc" Output: "abcabc" Explanation: We can alternate between the three different characters. Other valid outputs include "ababcc", "bacbac", etc.

Example 2:

Input: s = "aaab" Output: "" Explanation: The character 'a' appears 3 times in a string of length 4. Since (4+1)/2 = 2.5, no character can appear more than 2 times, making a valid arrangement impossible.

Example 3:

Input: s = "aab" Output: "aba" Explanation: We can place 'a' characters at positions 0 and 2, with 'b' at position 1.