How do you solve Reorganize String?

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.

What pattern does Reorganize String use?

The Pattern: Heap / Priority Queue (Greedy Frequency Scheduling) The Heuristic: Always pick the character with the highest remaining frequency that differs from the last placed character to maximize spacing and avoid adjacency conflicts.

Reorganize String — Heap / Priority Queue

Q: What is the time complexity of Reorganize String?

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).

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

Input: s = "aab"

Output: "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

Preview

The key recognition signals are 'no two adjacent characters are the same' and 'rearrangement of characters'…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

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)…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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.

Solution

Python

1class 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

1

Verify Rearrangement Feasibility by Frequency Analysis

3freq = Counter(s)
5if 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.

2

Build and Initialize Max-Heap with Character Frequencies

To prepare a max-heap data structure that prioritizes characters by their remaining frequency for greedy selection.

3

Greedily Construct Result by Alternating Characters Using Heap

To build the rearranged string by repeatedly selecting the most frequent character that differs from the previously used one.

4

Return the Final Reorganized String

To produce the final rearranged string by joining the accumulated characters.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 5 Critical

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.

Line 18 Critical

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.

Line 6 Critical

return ""

Return an empty string if rearrangement is impossible.

Early termination prevents unnecessary computation and ensures correctness by signaling no valid solution exists.

Full line-by-line criticality + rationale for all 14 lines available on Pro.

Test Your Understanding

Why must the maximum frequency of any character be at most (len(s) + 1) // 2 for a valid rearrangement to exist?

See the answer with Pro.

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

or drill a free problem

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)`