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
scan vary; note that if any character appears more than ⌊(n+1)/2⌋ times (where n is the length ofs), 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):
Java Code (Greedy with Priority Queue):
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):
Java Code (Even-Odd Placement):
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.
GET YOUR FREE
Coding Questions Catalog
