767. Reorganize String - Detailed Explanation

Problem Statement

Description:
Given a string s, rearrange its characters so that no two adjacent characters are the same. If such a rearrangement is not possible, return an empty string.

Example 1:

Input: "aab"
Output: "aba"
Explanation: One possible valid rearrangement is "aba" where no two adjacent characters are identical.

Example 2:

Input: "aaab"
Output: ""
Explanation: It is impossible to rearrange the string "aaab" such that no two adjacent characters are the same.

Constraints:

The string consists of lowercase English letters.
The length of s can vary; note that if any character appears more than ⌊(n+1)/2⌋ times (where n is the length of s), a valid rearrangement is impossible.

Intuition and Hints

Frequency Check:
For a valid rearrangement to exist, the maximum frequency of any character must not exceed ⌊(n+1)/2⌋. If it does, no valid answer exists.
Greedy Strategy:
A natural approach is to always place the character with the highest remaining frequency next, and then choose the next highest frequency character. This helps avoid adjacent duplicates.
Data Structures:
A max-heap (or priority queue) is useful to repeatedly extract the character with the highest count. Alternatively, if the alphabet size is small, you can use an even-odd index placement strategy.

Approaches

Approach 1: Greedy with Priority Queue (Max-Heap)

Explanation:

Count Frequencies:
Use a frequency counter to count occurrences of each character.
Feasibility Check:
If the maximum frequency is more than ⌊(n+1)/2⌋, return an empty string.
Max-Heap:
Build a max-heap (using negative frequencies in Python or a custom comparator in Java) to always get the character with the highest remaining frequency.
Reorganize:
Repeatedly remove the top two elements from the heap and append them to the result. Decrement their counts and push them back if they still have remaining frequency.
Leftover Character:
If one character remains at the end, append it to the result.
Return Result:
The final string is guaranteed not to have adjacent duplicates if a valid rearrangement exists.

Python Code (Greedy with Priority Queue):

Python3

. . . .

Java Code (Greedy with Priority Queue):

Java

. . . .

Approach 2: Even-Odd Placement Strategy

Explanation:

This alternate approach leverages the fact that if a valid rearrangement exists, you can distribute the most frequent character evenly in the result array:

Count Frequencies:
Determine the frequency of each character.
Feasibility Check:
If the most frequent character appears more than ⌊(n+1)/2⌋ times, return an empty string.
Placement in Even Indices:
Place the most frequent character at even indices (0, 2, 4, …) until its count is exhausted.
Fill Remaining Slots:
Place the remaining characters in the available slots (first fill even indices if available, then odd indices).
Return Result:
The final arrangement guarantees that no two adjacent characters are the same.

Python Code (Even-Odd Placement):

Python3

. . . .

Java Code (Even-Odd Placement):

Java

. . . .

Complexity Analysis

Greedy with Priority Queue Approach:
- Time Complexity: O(n log k) where k is the number of distinct characters (for English letters, k is at most 26, so it behaves nearly as O(n)).
- Space Complexity: O(n) for storing the heap and the result.
Even-Odd Placement Approach:
- Time Complexity: O(n)
- Space Complexity: O(n) for the result array.

Common Pitfalls & Edge Cases

Frequency Check:
Always verify that no character exceeds the allowable frequency of ⌊(n+1)/2⌋; otherwise, return an empty string.
Edge Cases:
- A string of length 0 or 1 should be returned as-is.
- When multiple characters have the same frequency, any valid permutation is acceptable.
Implementation Details:
- In the heap approach, be careful to update the frequency correctly and mark items as used.
- In the even-odd placement, ensure that when even positions are exhausted, you properly switch to odd positions.