Reorganize String
Problem
Given a string s, return any possible rearrangement of s such that no two adjacent characters are the same. If no such arrangement exists, return an empty string.
- 1 ≤ s.length ≤ 500
- s consists of lowercase English letters
Example
s = "aab""aba"The brute-force approach would try all permutations of the string and check if any satisfy the condition of no two adjacent characters being the same, which is factorial in time complexity and infeasible for large inputs. The critical insight is to recognize that if any character appears more than half the length of the string (rounded up), it is impossible to rearrange the string to avoid adjacent duplicates. For example, in "aaab", 'a' appears 3 times out of 4 characters, which is more than (4 + 1) // 2 = 2, so no valid rearrangement exists. This feasibility check is a quick filter that prevents unnecessary computation.
Approach
Straightforward Solution
A brute-force approach would generate all permutations of s and check each for validity, which is O(n!) and impractical for even moderate string lengths.
Core Observation
The fundamental truth is that no character can occupy more than half of the positions (rounded up) in the string if the rearrangement is to avoid adjacent duplicates. This is because characters must be interleaved with others to separate identical characters.
Path to Optimal
The key recognition signals are 'no two adjacent characters are the same' and 'rearrangement of characters'. These indicate a greedy approach using a max-heap (priority queue) to always pick the character with the highest remaining frequency that is not the same as the previously placed character. This approach ensures that the most frequent characters are spaced out as much as possible.
Optimal Approach
Count the frequency of each character and verify feasibility. Use a max-heap to store characters by their negative frequency (to simulate max-heap in Python). At each step, pop the character with the highest frequency that is not the same as the previously used character, append it to the result, and then push back the previous character if it still has remaining frequency. This process continues until the heap is empty, guaranteeing a valid rearrangement if one exists.
Time
O(n log k)
Counting frequencies takes O(n). Building the heap takes O(k), where k is the number of unique characters. Each character is pushed and popped at most its frequency times, totaling O(n) heap operations, each O(log k). Since k ≤ 26 for lowercase letters, this is effectively O(n).
Space
O(k)
The frequency map and heap store up to k unique characters, where k ≤ 26 for lowercase English letters, so space is O(1) auxiliary with respect to input size.
Pattern Spotlight
Heap / Priority Queue (Greedy Frequency Scheduling)
Always pick the character with the highest remaining frequency that differs from the last placed character to maximize spacing and avoid adjacency conflicts.
Solution
| 1 | class Solution: |
| 2 | def reorganizeString(self, s: str) -> str: |
| 3 | freq = Counter(s) |
| 4 | |
| 5 | if max(freq.values()) > (len(s) + 1) // 2: |
| 6 | return "" |
| 7 | |
| 8 | heap = [(-count, char) for char, count in freq.items()] |
| 9 | heapq.heapify(heap) |
| 10 | |
| 11 | prev = (0, "") |
| 12 | res = [] |
| 13 | |
| 14 | while heap: |
| 15 | count, char = heapq.heappop(heap) |
| 16 | res.append(char) |
| 17 | |
| 18 | if prev[0] < 0: |
| 19 | heapq.heappush(heap, prev) |
| 20 | |
| 21 | prev = (count + 1, char) |
| 22 | |
| 23 | return "".join(res) |
Step-by-Step Solution
Verify Rearrangement Feasibility by Frequency Analysis
| 3 | freq = Counter(s) |
| 5 | if max(freq.values()) > (len(s) + 1) // 2: |
| 6 | return "" |
Objective
To determine early if a valid rearrangement is impossible by checking the maximum character frequency.
Key Insight
If any character's count exceeds half the length of the string (rounded up), no rearrangement can prevent adjacent duplicates. This check quickly filters out impossible cases, saving computation time by returning an empty string immediately.
Interview Quick-Check
Core Logic
The feasibility condition max(freq.values()) <= (len(s) + 1) // 2 ensures that characters can be interleaved without adjacency.
Common Pitfalls & Bugs
Forgetting to perform this check can lead to infinite loops or incorrect results when no valid rearrangement exists.
Build and Initialize Max-Heap with Character Frequencies
| 8 | heap = [(-count, char) for char, count in freq.items()] |
| 9 | heapq.heapify(heap) |
Objective
To prepare a max-heap data structure that prioritizes characters by their remaining frequency for greedy selection.
Key Insight
Using a max-heap allows efficient retrieval of the character with the highest remaining count. Storing counts as negative values leverages Python's min-heap implementation to simulate a max-heap. This structure is essential for the greedy strategy to always pick the most frequent character available.
Interview Quick-Check
Core Logic
Heapifying the list of (-count, char) pairs enables O(log k) retrieval of the character with the highest frequency.
Complexity
Heap operations are efficient since the number of unique characters k is at most 26, making heap operations effectively constant time.
Greedily Construct Result by Alternating Characters Using Heap
| 11 | prev = (0, "") |
| 12 | res = [] |
| 14 | while heap: |
| 15 | count, char = heapq.heappop(heap) |
| 16 | res.append(char) |
| 18 | if prev[0] < 0: |
| 19 | heapq.heappush(heap, prev) |
| 21 | prev = (count + 1, char) |
Objective
To build the rearranged string by repeatedly selecting the most frequent character that differs from the previously used one.
Key Insight
By always choosing the character with the highest remaining frequency that is not the same as the last appended character, the algorithm spaces out identical characters to avoid adjacency. The previous character is stored and reinserted into the heap only after a different character is placed, ensuring no two identical characters are adjacent. This greedy approach guarantees a valid rearrangement if one exists.
Interview Quick-Check
Core Logic
The algorithm maintains a 'prev' variable to hold the last used character and its remaining count, pushing it back into the heap only after placing a different character to prevent immediate repetition.
State & Boundaries
The loop continues until the heap is empty, ensuring all characters are placed.
Common Pitfalls & Bugs
Failing to update 'prev' correctly or pushing it back too early can cause adjacent duplicates or infinite loops.
Return the Final Reorganized String
| 23 | return "".join(res) |
Objective
To produce the final rearranged string by joining the accumulated characters.
Key Insight
Joining the list of characters into a string is the final step that converts the internal representation into the required output format. Since the algorithm guarantees no two adjacent characters are the same, the returned string satisfies the problem constraints.
Interview Quick-Check
Core Logic
Joining the list into a string returns the final rearranged string that meets the adjacency condition.
Line Analysis
This solution has 5 Critical lines interviewers watch for.
if max(freq.values()) > (len(s) + 1) // 2:Check if the maximum character frequency exceeds the allowed threshold.
This condition quickly identifies impossible cases where a character appears more than half the string length (rounded up), making rearrangement without adjacent duplicates impossible.
if prev[0] < 0:If the previous character still has remaining count, push it back into the heap.
Reinserting the previous character only after placing a different character ensures no two identical characters are adjacent and maintains correct frequency counts.
return ""Return an empty string if rearrangement is impossible.
Early termination prevents unnecessary computation and ensures correctness by signaling no valid solution exists.
count, char = heapq.heappop(heap)Pop the character with the highest remaining frequency from the heap.
Selecting the most frequent character available maximizes spacing between identical characters, reducing adjacency risk.
prev = (count + 1, char)Update the previous character to the current one with decremented count.
Decrementing the count reflects the usage of one occurrence of the character, and storing it as previous prevents immediate reuse, enforcing the adjacency rule.
freq = Counter(s)Count the frequency of each character in the input string.
Frequency counting is essential to understand the distribution of characters and to detect if any character appears too frequently to allow a valid rearrangement.
heapq.heapify(heap)Transform the list into a heap data structure.
Heapifying organizes the data to allow O(log k) insertion and extraction of the highest frequency character, which is critical for the greedy selection process.
heapq.heappush(heap, prev)Push the previous character back into the heap for future selection.
This step preserves the availability of characters with remaining counts, enabling their eventual placement while avoiding immediate repetition.
heap = [(-count, char) for char, count in freq.items()]Create a list of tuples with negative counts and characters for heap initialization.
Storing counts as negative values allows Python's min-heap to function as a max-heap, enabling efficient retrieval of the most frequent character.
prev = (0, "")Initialize the previous character tracker with zero count and empty character.
This variable holds the character last appended to the result and its remaining count, enabling the algorithm to avoid placing the same character consecutively.
res.append(char)Append the selected character to the result list.
Adding the chosen character to the result builds the output string incrementally while respecting the adjacency constraint.
while heap:Loop while there are characters left in the heap to process.
This loop drives the greedy construction of the rearranged string by repeatedly selecting the next character to append.
return "".join(res)Join the list of characters into a single string and return it.
Converting the accumulated characters into a string produces the final output in the required format.
res = []Initialize an empty list to accumulate the result characters.
Using a list for character accumulation is efficient for appending and later joining into the final string.
Test Your Understanding
Why must the maximum frequency of any character be at most (len(s) + 1) // 2 for a valid rearrangement to exist?
Because if a character appears more than half the length of the string (rounded up), it is impossible to separate all its occurrences with other characters, inevitably causing at least two identical characters to be adjacent.
Related Problems
Heaps pattern
Don't just read it. Drill it.
Reconstruct Reorganize String from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Reorganize String drill