Loading problems...
TL;DR: The optimal solution uses a Max-Heap to greedily append the most frequent remaining character that is different from the previously appended character.
The Reorganize String problem asks us to permute a given string s such that no two adjacent characters are identical. If such a rearrangement is impossible (e.g., one character appears too frequently to be spaced out), we must return an empty string. This is a classic scheduling problem disguised as string manipulation, requiring us to manage resource availability (character counts) dynamically.
The brute force approach involves generating every possible permutation of the input string s and checking each one for validity.
s.permutation[i] == permutation[i-1] for any index i."".Pseudo-code:
textfunction solve(s): permutations = generate_all_permutations(s) for p in permutations: valid = true for i from 1 to length(p) - 1: if p[i] == p[i-1]: valid = false break if valid: return p return ""
Why this fails: The time complexity of this approach is , where is the length of the string. With the constraint , the number of permutations is astronomically large (). This will immediately result in a Time Limit Exceeded (TLE) error. We need a constructive approach rather than a search-based approach.
The fundamental intuition for the LeetCode 767 solution is based on the Greedy Principle. To minimize the risk of running out of "buffer" characters to place between identical characters, we should always try to place the character that has the highest remaining frequency.
If the most frequent character appears more than times, it is mathematically impossible to rearrange the string without adjacent duplicates (by the Pigeonhole Principle). We can return "" immediately in this case.
If a valid arrangement is possible, we use a Max-Heap to manage character frequencies.
Visual Description: Imagine the heap as a dynamic ranking board. At the top is the character with the most urgent need to be placed.

Let's trace s = "aab".
{'a': 2, 'b': 1}.[(2, 'a'), (1, 'b')]. prev is None.Iteration 1:
(2, 'a')."a".(1, 'a').prev was None, so nothing is pushed back.prev = (1, 'a').[(1, 'b')].Iteration 2:
(1, 'b')."ab".(0, 'b').prev was (1, 'a'). Push (1, 'a') back to heap.prev = (0, 'b').[(1, 'a')].Iteration 3:
(1, 'a')."aba".(0, 'a').prev was (0, 'b'). Count is 0, so do not push back.prev = (0, 'a').End: Heap empty. Return "aba".
The correctness relies on the invariant that we always reduce the count of the most frequent character. By always picking the element with the highest remaining frequency, we ensure that the most "problematic" character (the one most likely to cause a collision) is spaced out as evenly as possible. The "hold and push back" mechanism guarantees strictly that .
If the maximum frequency constraint () holds, a valid arrangement always exists. The greedy strategy constructs one such arrangement by ensuring we never leave a high-frequency character stranded at the end without valid separators.
cpp#include <string> #include <vector> #include <queue> #include <unordered_map> using namespace std; class Solution { public: string reorganizeString(string s) { unordered_map<char, int> counts; for (char c : s) { counts[c]++; } // Max-heap storing pairs of (frequency, character) priority_queue<pair<int, char>> pq; for (auto& entry : counts) { // Early exit check: if any char count > (N + 1) / 2, impossible if (entry.second > (s.length() + 1) / 2) { return ""; } pq.push({entry.second, entry.first}); } string result = ""; pair<int, char> prev = {-1, '#'}; // Placeholder for blocked char while (!pq.empty()) { pair<int, char> current = pq.top(); pq.pop(); result += current.second; current.first--; // If we have a valid previous character blocked, put it back if (prev.first > 0) { pq.push(prev); } // Block the current character for the next iteration prev = current; } if (result.length() != s.length()) { return ""; } return result; } };
javaimport java.util.PriorityQueue; import java.util.HashMap; import java.util.Map; class Solution { public String reorganizeString(String s) { Map<Character, Integer> counts = new HashMap<>(); for (char c : s.toCharArray()) { counts.put(c, counts.getOrDefault(c, 0) + 1); } // Max-heap ordered by frequency descending PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]); for (Map.Entry<Character, Integer> entry : counts.entrySet()) { if (entry.getValue() > (s.length() + 1) / 2) { return ""; } // Store as [count, char_code] pq.offer(new int[]{entry.getValue(), entry.getKey()}); } StringBuilder sb = new StringBuilder(); int[] prev = null; // Holds the character blocked from immediate reuse while (!pq.isEmpty()) { int[] current = pq.poll(); sb.append((char)current[1]); current[0]--; // If there was a previous character waiting, add it back to heap if (prev != null && prev[0] > 0) { pq.offer(prev); } // Block current character prev = current; } if (sb.length() != s.length()) return ""; return sb.toString(); } }
pythonimport heapq from collections import Counter class Solution: def reorganizeString(self, s: str) -> str: counts = Counter(s) # Python's heapq is a min-heap. We store negative counts to simulate max-heap. max_heap = [] for char, count in counts.items(): if count > (len(s) + 1) / 2: return "" heapq.heappush(max_heap, (-count, char)) result = [] prev_count, prev_char = 0, '' while max_heap: count, char = heapq.heappop(max_heap) result.append(char) # Since count is negative, we add 1 to decrement frequency towards 0 count += 1 # If the PREVIOUS character still has count left, push it back if prev_count < 0: heapq.heappush(max_heap, (prev_count, prev_char)) # Update previous to current prev_count, prev_char = count, char final_str = "".join(result) if len(final_str) != len(s): return "" return final_str
Let be the length of the string s and be the number of unique characters (at most 26 for lowercase English letters).
The Heap - Scheduling pattern used in the LeetCode 767 solution is highly versatile. It applies to problems where you must interleave resources or manage tasks based on priority/cost.
K quality workers while iterating through wage-to-quality ratios.Why does my solution TLE even with a Heap?
Why does my Python solution output the wrong order?
heapq is a Min-Heap.Why does my solution fail on "aaab"?
max_freq > (N + 1) / 2.Why is my space complexity O(N)?