282. Reorganize String
🔗 LeetCode Problem: 767. Reorganize String
📊 Difficulty: Medium
🏷️ Topics: Hash Table, String, Greedy, Sorting, Heap (Priority Queue), Counting
Problem Statement
Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.
Return any possible rearrangement of s or return "" if not possible.
Example 1:
Input: s = "aab"
Output: "aba"
Example 2:
Input: s = "aaab"
Output: ""
Constraints:
- 1 <= s.length <= 500
- s consists of lowercase English letters
🌟 Understanding the Problem
What does "no two adjacent same" mean?
Valid: "aba"
a b a
↑ ↑ ↑
Different neighbors
Invalid: "aab"
a a b
↑ ↑
Same neighbors! ✗
Valid: "abab"
a b a b
All neighbors different ✓
When is it impossible?
Example: s = "aaab"
Frequency: a=3, b=1
Try to arrange:
a _ a _ a
Need 2 different characters between a's
But only have 1 b!
a b a ? a ✗
Cannot separate all a's!
Impossible! ✗
General rule:
If most frequent character appears > (n+1)/2 times
→ Impossible!
Key Observations:
1. Greedy strategy works
→ Always place most frequent available character
→ Spreads out frequent characters
2. Need to avoid same adjacent
→ Can't place character just placed
→ Need to "cool down" like Task Scheduler!
3. Check impossibility early
→ If maxFreq > (n+1)/2 → return ""
→ Save time trying impossible cases
🌟 The Natural Thinking Process
When you first see this problem:
Question: Rearrange so no two adjacent same
First Thought: "Try all permutations, check if valid"
- Generate all arrangements
- Check each if no adjacent same
- Return first valid one
Is this optimal? NO (n! permutations!), but conceptually simple!
The Evolution:
BRUTE FORCE THINKING:
"Try all permutations"
Time: O(n! × n) - factorial!
Problem: Way too slow! 😱
⬇
REALIZATION 1:
"Greedy might work!"
"Place most frequent character first"
"Spreads out frequent characters"
⬇
OPTIMIZATION 1: Greedy with Max-Heap
"Always pick most frequent available"
"Use cooldown like Task Scheduler"
Time: O(n log k) where k = unique chars
⬇
REALIZATION 2:
"Can detect impossibility early!"
"If maxFreq > (n+1)/2 → impossible"
⬇
OPTIMIZATION 2: Early Impossibility Check
"Check before attempting"
"Same greedy, but faster rejection"
Time: O(n log k) but avoids impossible cases ✨
🎯 Approach 1: Greedy with Max-Heap ⭐⭐⭐
The Optimal Solution (Without Early Check)
The Thought Process:
Step 1: Count character frequencies
Step 2: Use max-heap (by frequency)
- Always pick most frequent available
- Place character
- Put on "cooldown" (can't use immediately)
Step 3: After placing, add back to heap
- Decrease frequency
- If count > 0, add back
Similar to Task Scheduler Problem 280! ✨
WHY Greedy Works - Critical Reasoning
The Core Question:
Why does always picking most frequent work?
Could there be a case where picking less frequent is better?
Answer Through Detailed Reasoning:
PRINCIPLE: Spread Out Frequent Characters
═══════════════════════════════════════════════════════════════
Problem with frequent characters:
If character appears k times in string of length n,
need to place k characters with k-1 gaps between them.
If k is too large, we run out of other characters to fill gaps!
Strategy:
Place most frequent characters FIRST
→ Uses them up early
→ Gives more chances to separate them
→ Less likely to get stuck
Example: s = "aaabbc"
Frequencies: a=3, b=2, c=1
Greedy (pick most frequent first):
Pick a: result = "a"
Pick b: result = "ab"
Pick a: result = "aba"
Pick b: result = "abab"
Pick a: result = "ababa"
Pick c: result = "ababac" ✓
Wrong strategy (pick least frequent first):
Pick c: result = "c"
Pick b: result = "cb"
Pick b: result = "cbc" (or "bcb")
Pick a: result = "cbca"
Pick a: result = "cbcaa" ✗
Two a's adjacent! Failed!
═══════════════════════════════════════════════════════════════
WHY Most Frequent First?
═══════════════════════════════════════════════════════════════
Mathematical reasoning:
If most frequent char has count = maxFreq,
needs (maxFreq - 1) gaps to separate all occurrences.
Other characters must fill these gaps!
By placing most frequent first:
- Creates structure: [A][?][A][?][A]...
- Other chars fill [?] positions
- If we have enough other chars → success!
If we place most frequent LAST:
- Other chars already placed
- Might have adjacent duplicates already!
- Less room to maneuver
- More likely to fail
Greedy = maximize chances of success! ✓
═══════════════════════════════════════════════════════════════
PROOF: Why Greedy is Optimal
═══════════════════════════════════════════════════════════════
Claim: If any arrangement exists, greedy finds one.
Proof by contradiction:
Assume greedy fails but valid arrangement exists.
Greedy fails → gets stuck → adjacent same or impossible
But if valid arrangement exists:
→ All characters can be separated
→ Most frequent char is separated in valid arrangement
Since most frequent is most "dangerous" (hardest to separate),
if valid arrangement separates it, greedy can too!
Greedy places most frequent first → gives best chance
If greedy fails → truly impossible!
Conclusion: Greedy is OPTIMAL! ✨
═══════════════════════════════════════════════════════════════
COOLDOWN MECHANISM (Like Task Scheduler)
═══════════════════════════════════════════════════════════════
Why can't we use a character just placed?
If we just placed 'a':
result = "...a"
If we place 'a' again:
result = "...aa" ✗
Adjacent same! Invalid!
Need "cooldown":
After placing 'a', must place different character next
Then 'a' available again
Implementation:
Keep reference to last placed character
Don't pick it again from heap immediately
Add it back after picking next character
This ensures no adjacent same! ✓
Visual Tracking - Complete Example
Input: s = "aab"
═══════════════════════════════════════════════════════════════
STEP 1: Count Frequencies
═══════════════════════════════════════════════════════════════
Frequency map:
a: 2
b: 1
═══════════════════════════════════════════════════════════════
STEP 2: Build Max-Heap
═══════════════════════════════════════════════════════════════
Max-heap by frequency:
Heap: [(a, 2), (b, 1)]
↑
most frequent
═══════════════════════════════════════════════════════════════
STEP 3: Greedy Construction
═══════════════════════════════════════════════════════════════
Result: ""
Previous: null
─────────────────────────────────────────────────────────────
Iteration 1
─────────────────────────────────────────────────────────────
Heap: [(a, 2), (b, 1)]
Pick most frequent: (a, 2)
Place 'a': result = "a"
Decrease count: (a, 1)
Previous: (a, 1) (on cooldown)
Heap: [(b, 1)]
─────────────────────────────────────────────────────────────
Iteration 2
─────────────────────────────────────────────────────────────
Heap: [(b, 1)]
Previous: (a, 1)
Pick most frequent: (b, 1)
Place 'b': result = "ab"
Decrease count: (b, 0) → done with b
Add previous back: (a, 1)
Previous: (b, 0) → null (done)
Heap: [(a, 1)]
─────────────────────────────────────────────────────────────
Iteration 3
─────────────────────────────────────────────────────────────
Heap: [(a, 1)]
Previous: null
Pick: (a, 1)
Place 'a': result = "aba"
Decrease: (a, 0) → done
Previous: null
Heap: []
═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════
Final string: "aba"
Verification:
a b a
↑ ↑ ↑
All different neighbors ✓
Success! ✓
Example 2 - Impossible Case
Input: s = "aaab"
═══════════════════════════════════════════════════════════════
STEP 1: Count Frequencies
═══════════════════════════════════════════════════════════════
Frequency map:
a: 3
b: 1
═══════════════════════════════════════════════════════════════
STEP 2: Build Heap
═══════════════════════════════════════════════════════════════
Heap: [(a, 3), (b, 1)]
═══════════════════════════════════════════════════════════════
STEP 3: Greedy Construction
═══════════════════════════════════════════════════════════════
Result: ""
─────────────────────────────────────────────────────────────
Iteration 1
─────────────────────────────────────────────────────────────
Pick (a, 3): result = "a"
Previous: (a, 2)
Heap: [(b, 1)]
─────────────────────────────────────────────────────────────
Iteration 2
─────────────────────────────────────────────────────────────
Pick (b, 1): result = "ab"
Add previous (a, 2) back
Previous: (b, 0) → null
Heap: [(a, 2)]
─────────────────────────────────────────────────────────────
Iteration 3
─────────────────────────────────────────────────────────────
Pick (a, 2): result = "aba"
Previous: (a, 1)
Heap: []
─────────────────────────────────────────────────────────────
Iteration 4 - STUCK!
─────────────────────────────────────────────────────────────
Heap: []
Previous: (a, 1) still has count!
Can't place from empty heap
Can't place previous (would be adjacent)
STUCK! ✗
═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════
Return: "" (impossible)
Why?
3 a's need 2 gaps
Only 1 b available
Cannot separate all a's! ✗
Implementation
import java.util.*;
/**
* Greedy with Max-Heap
* Time: O(n log k) where k = unique chars
* Space: O(k)
*/
class Solution {
public String reorganizeString(String s) {
// Count frequencies
Map<Character, Integer> freqMap = new HashMap<>();
for (char c : s.toCharArray()) {
freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
}
// Max-heap by frequency
PriorityQueue<Map.Entry<Character, Integer>> maxHeap =
new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
maxHeap.addAll(freqMap.entrySet());
StringBuilder result = new StringBuilder();
Map.Entry<Character, Integer> previous = null;
while (!maxHeap.isEmpty()) {
// Pick most frequent
Map.Entry<Character, Integer> current = maxHeap.poll();
result.append(current.getKey());
// Add previous back (it's now cooled down)
if (previous != null && previous.getValue() > 0) {
maxHeap.offer(previous);
}
// Decrease current count and make it previous
current.setValue(current.getValue() - 1);
previous = current;
}
// Check if we used all characters
// If previous still has count, we got stuck
if (previous != null && previous.getValue() > 0) {
return "";
}
return result.toString();
}
}
⏰ Time: O(n log k) where k ≤ 26 (unique chars)
💾 Space: O(k)
🎯 Approach 2: Greedy with Early Impossibility Check (Enhanced) ⭐⭐⭐
The Enhanced Optimal Solution
The Evolution of Thought:
Approach 1 works but tries impossible cases
⬇
Observation: "Can detect impossibility early!"
⬇
Enhanced: "Check before attempting greedy!"
Understanding Impossibility - Complete Mathematical Proof
The Core Question:
When is reorganization impossible?
Why is the formula maxFreq > (n+1)/2?
Answer Through Detailed Proof:
IMPOSSIBILITY CONDITION - Complete Derivation
═══════════════════════════════════════════════════════════════
Setup:
n = string length
Most frequent char appears maxFreq times
Other chars appear (n - maxFreq) times total
Goal: Separate all occurrences of most frequent char
Strategy:
Place most frequent char in pattern:
[A][?][A][?][A]...[A]
If A appears maxFreq times:
- Need (maxFreq - 1) gaps between them
- Each gap needs at least 1 other character
Required other characters: maxFreq - 1
Available other characters: n - maxFreq
Condition for possibility:
n - maxFreq >= maxFreq - 1
Rearrange:
n - maxFreq >= maxFreq - 1
n >= 2×maxFreq - 1
n + 1 >= 2×maxFreq
(n + 1) / 2 >= maxFreq
Or equivalently:
maxFreq <= (n + 1) / 2
Impossibility:
maxFreq > (n + 1) / 2 ✗
═══════════════════════════════════════════════════════════════
WHY (n+1)/2 and not n/2?
═══════════════════════════════════════════════════════════════
Consider edge cases:
Case 1: n = 4 (even)
Formula: (4+1)/2 = 2.5 → ceil = 3
If maxFreq = 3:
Pattern: [A][?][A][?][A]
Need 2 gaps, have 4-3=1 other char
1 < 2 → Impossible ✗
If maxFreq = 2:
Pattern: [A][?][A]
Need 1 gap, have 4-2=2 other chars
2 >= 1 → Possible ✓
Example: "aabb" → "abab" ✓
Case 2: n = 5 (odd)
Formula: (5+1)/2 = 3
If maxFreq = 3:
Pattern: [A][?][A][?][A]
Need 2 gaps, have 5-3=2 other chars
2 >= 2 → Exactly enough! ✓
Example: "aaabc" → "abaca" ✓
If maxFreq = 4:
Pattern: [A][?][A][?][A][?][A]
Need 3 gaps, have 5-4=1 other char
1 < 3 → Impossible ✗
The +1 handles both even and odd correctly!
For even n: maxFreq can be at most n/2
For odd n: maxFreq can be at most (n+1)/2
Formula (n+1)/2 unifies both! ✓
═══════════════════════════════════════════════════════════════
INTUITIVE UNDERSTANDING
═══════════════════════════════════════════════════════════════
Think of the string as pairs:
[AB][AB][AB]...
If most frequent char > half the string:
Can't pair it with different chars
Will have adjacent duplicates!
Example: "aaab"
n = 4, maxFreq = 3
3 > (4+1)/2 = 2.5
3 > 2.5 → Impossible ✓
Cannot pair all a's with different chars!
Visual Tracking - With Early Check
Input: s = "aaab"
═══════════════════════════════════════════════════════════════
EARLY IMPOSSIBILITY CHECK
═══════════════════════════════════════════════════════════════
Count frequencies:
a: 3
b: 1
Find max frequency:
maxFreq = 3
Check condition:
n = 4
(n + 1) / 2 = (4 + 1) / 2 = 2.5
maxFreq > (n + 1) / 2?
3 > 2.5? YES ✗
Conclusion: IMPOSSIBLE!
Return: "" immediately
Skip greedy construction! ✓
═══════════════════════════════════════════════════════════════
Input: s = "aab"
Count frequencies:
a: 2
b: 1
Check condition:
n = 3
(n + 1) / 2 = 2
maxFreq > (n + 1) / 2?
2 > 2? NO ✓
Conclusion: POSSIBLE!
Proceed with greedy construction...
[Same as Approach 1]
Result: "aba" ✓
Implementation
import java.util.*;
/**
* Greedy with early impossibility check
* Time: O(n log k) where k = unique chars
* Space: O(k)
*/
class Solution {
public String reorganizeString(String s) {
int n = s.length();
// Count frequencies
Map<Character, Integer> freqMap = new HashMap<>();
int maxFreq = 0;
for (char c : s.toCharArray()) {
freqMap.put(c, freqMap.getOrDefault(c, 0) + 1);
maxFreq = Math.max(maxFreq, freqMap.get(c));
}
// Early impossibility check
if (maxFreq > (n + 1) / 2) {
return "";
}
// Max-heap by frequency
PriorityQueue<Map.Entry<Character, Integer>> maxHeap =
new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
maxHeap.addAll(freqMap.entrySet());
StringBuilder result = new StringBuilder();
Map.Entry<Character, Integer> previous = null;
while (!maxHeap.isEmpty()) {
Map.Entry<Character, Integer> current = maxHeap.poll();
result.append(current.getKey());
if (previous != null && previous.getValue() > 0) {
maxHeap.offer(previous);
}
current.setValue(current.getValue() - 1);
previous = current;
}
// With early check, this should never happen
// But kept for safety
if (previous != null && previous.getValue() > 0) {
return "";
}
return result.toString();
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.reorganizeString("aab")); // "aba"
System.out.println(sol.reorganizeString("aaab")); // ""
System.out.println(sol.reorganizeString("vvvlo")); // "vovlv"
}
}
⏰ Time: O(n log k) - Same but faster rejection
💾 Space: O(k)
Why Enhanced is Better:
✓ Same complexity but faster on impossible cases
✓ Early rejection saves greedy construction
✓ Mathematical check is O(n), very cheap
✓ More elegant and clear
Example: s = "aaaaaa" (impossible)
Without check: Tries greedy, gets stuck, returns ""
With check: Immediately returns "" after counting
Much faster! ✨
📊 Approach Comparison - The Growth Journey
┌─────────────┬─────────────┬──────────┬──────────────────────┐
│ Approach │ Time │ Space │ Key Insight │
├─────────────┼─────────────┼──────────┼──────────────────────┤
│ Brute Force │ O(n! × n) │ O(n) │ Try all permutations │
│ Greedy │ O(n log k) │ O(k) │ Most frequent first │
│ Enhanced │ O(n log k) │ O(k) │ Early impossibility │
└─────────────┴─────────────┴──────────┴──────────────────────┘
THE COMPLETE LEARNING PROGRESSION:
Level 1: Brute Force (Conceptual)
Thought: "Try all permutations"
Works? YES for small input ✓
Optimal? NO ✗
Time: O(n!)
Problem: Factorial explosion!
Level 2: Greedy Insight
Observation: "Most frequent is hardest to separate"
Idea: "Place most frequent first!"
Level 3: Greedy with Heap
Implementation: Max-heap by frequency
Cooldown: Like Task Scheduler
Result: O(n log k) ✓
Works: Finds valid arrangement or detects impossible
Level 4: Mathematical Insight
Observation: "Can detect impossibility early!"
Formula: maxFreq > (n+1)/2 → impossible
Proof: Need (maxFreq-1) gaps, have (n-maxFreq) others
Level 5: Enhanced Solution
Implementation: Early check + greedy
Result: Same O(n log k) but faster rejection ✓
Perfect: Mathematical elegance! ✨
Growth: Learned greedy + impossibility formula!
CONCRETE EXAMPLE:
s = 100 'a's (impossible)
Without check:
- Build heap
- Try greedy construction
- Get stuck
- Return ""
Time: O(100 log 1) = O(100)
With check:
- Count: a=100
- Check: 100 > (100+1)/2 = 50.5
- Return "" immediately
Time: O(100) but much faster constant
Early rejection saves work! ✨
💡 Key Learnings - Your Complete Growth
WHAT YOU LEARNED:
1. GREEDY CORRECTNESS:
✓ Most frequent first spreads them out
✓ Creates structure for others to fill
✓ If greedy fails → truly impossible
✓ Proved greedy is optimal!
2. COOLDOWN MECHANISM:
✓ Can't use just-placed character
✓ Keep reference to previous
✓ Add back after placing next
✓ Similar to Task Scheduler pattern!
3. IMPOSSIBILITY FORMULA:
✓ maxFreq > (n+1)/2 → impossible
✓ Need (maxFreq-1) gaps
✓ Have (n-maxFreq) other chars
✓ Must have enough to fill gaps!
4. WHY (n+1)/2:
✓ Handles both even and odd
✓ Even: max = n/2
✓ Odd: max = (n+1)/2
✓ Unified formula!
5. PATTERN RECOGNITION:
✓ Similar to Task Scheduler (280)
✓ Greedy with heap
✓ Cooldown mechanism
✓ Frequency-based scheduling!
INTERVIEW STRATEGY:
Progressive Presentation:
"I see this as a greedy problem:
Key insight: Place most frequent characters first
Why? Spreads them out, maximizes separation chances
Approach:
1. Count character frequencies
2. Check impossibility early:
If maxFreq > (n+1)/2 → return ""
Why? Need (maxFreq-1) gaps, have (n-maxFreq) others
Must have enough others to separate
3. Use max-heap by frequency
4. Greedy construction:
- Pick most frequent available
- Place character
- Cooldown (can't use immediately)
- Add back to heap after placing next
5. Build result string
Time: O(n log k) where k ≤ 26
Space: O(k)
Let me explain why greedy works:
[explain most frequent first]
[explain mathematical impossibility]
[explain cooldown mechanism]
This is optimal!"
Shows:
✓ Greedy strategy understanding
✓ Mathematical impossibility proof
✓ Cooldown mechanism
✓ Pattern recognition
✓ Optimal solution
This is REAL mastery! 🌱→🌳→🏆
⚠️ Common Mistakes
Mistake 1: Using min-heap instead of max-heap
// ❌ WRONG - Min-heap picks least frequent!
PriorityQueue<Map.Entry<Character, Integer>> minHeap =
new PriorityQueue<>((a,b) -> a.getValue() - b.getValue());
// ✓ CORRECT - Max-heap picks most frequent
PriorityQueue<Map.Entry<Character, Integer>> maxHeap =
new PriorityQueue<>((a,b) -> b.getValue() - a.getValue());
Mistake 2: Not handling previous character
// ❌ WRONG - May place same char adjacent
while (!heap.isEmpty()) {
current = heap.poll();
result.append(current.getKey());
current.setValue(current.getValue() - 1);
if (current.getValue() > 0) {
heap.offer(current); // Immediately back in heap!
}
}
// ✓ CORRECT - Cooldown mechanism
Map.Entry<Character, Integer> previous = null;
while (!heap.isEmpty()) {
current = heap.poll();
result.append(current.getKey());
if (previous != null && previous.getValue() > 0) {
heap.offer(previous); // Add previous back
}
current.setValue(current.getValue() - 1);
previous = current; // Current becomes previous
}
Mistake 3: Wrong impossibility check
// ❌ WRONG - Uses n/2 instead of (n+1)/2
if (maxFreq > n / 2) return "";
// ✓ CORRECT - Uses (n+1)/2
if (maxFreq > (n + 1) / 2) return "";
Mistake 4: Not checking if previous has remaining count
// ❌ WRONG - Doesn't detect getting stuck
return result.toString();
// ✓ CORRECT - Check if previous still has count
if (previous != null && previous.getValue() > 0) {
return ""; // Got stuck!
}
return result.toString();
🎯 Pattern Recognition
Problem Type: Greedy String Rearrangement
Core Pattern: Frequency-Based Greedy with Cooldown
When to Apply:
✓ Rearrange with constraints on adjacent elements
✓ Frequency-based placement
✓ Greedy strategy (most frequent first)
✓ Cooldown/separation requirements
Recognition Keywords:
- "rearrange"
- "no two adjacent same"
- "reorganize"
- "separate"
Similar Problems:
- Task Scheduler (LC 621) - Same greedy pattern!
- Rearrange String k Distance Apart (LC 358)
- Distance Between Same Characters (variation)
Key Components:
┌────────────────────────────────────────────┐
│ Frequency Count: Know character counts │
│ Max-Heap: Pick most frequent │
│ Cooldown: Can't use just-placed │
│ Impossibility: maxFreq > (n+1)/2 │
│ Greedy: Most frequent first │
└────────────────────────────────────────────┘
📝 Quick Revision Notes
🎯 Core Concept:
Rearrange so no two adjacent same. Greedy: Always place most frequent available. Use max-heap by frequency. Cooldown: Can't use just-placed character (keep as previous). Impossibility: If maxFreq > (n+1)/2, can't separate all occurrences. Check early to save time!
⚡ Quick Implementation:
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class Solution {
public String reorganizeString(String s) {
// return maxHeap(s);
return maxHeapEarly(s);
}
private String maxHeapEarly(String s) {
// step 1: create freq map
// "aab" => {a:2,b:1}
HashMap<Character, Integer> freqMap = new HashMap<>();
for (char ch : s.toCharArray()) {
freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
}
// step 2: get max freq
int maxFreq = 0;
for (int val : freqMap.values()) {
maxFreq = Math.max(maxFreq, val);
}
// step 3: deriving the formula
// len(s) = n
// Max freq of some character = maxFreq
// A _ A _ A _ A _ A
// Mimumum gaps we need to have = maxFreq - 1
// Remaining characters = n - maxFreq
// n - maxFreq >= maxFreq - 1
// (n+1)/2 >= maxFreq
// Opposite: if maxFreq > (n+1)/2 => NOT POSSIBLE
if (maxFreq > (s.length() + 1) / 2) {
return "";
}
// step 4: else proceed normal
return maxHeap(s);
}
private String maxHeap(String s) {
// step 1: create freq map
// "aab" => {a:2,b:1}
HashMap<Character, Integer> freqMap = new HashMap<>();
for (char ch : s.toCharArray()) {
freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);
}
// step 2: put into a PQ where higher freq char always
// comes first (max heap)
PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
(entry1, entry2) -> entry2.getValue() - entry1.getValue());
// GOTCHA: good
pq.addAll(freqMap.entrySet());
StringBuilder sb = new StringBuilder();
Map.Entry<Character, Integer> previous = null;
// step 3: loop till we have elements to be processes
while (!pq.isEmpty()) {
// step 4: get highest freq element now
// we get a:2 here
Map.Entry<Character, Integer> polled = pq.poll();
sb.append(polled.getKey()); // "a" gets created here
// step 5: since no adjacent chars are to be equal, we
// need to put this in cooldown with freq reduced by 1
// (kind of temporarily hold and not to be used).
// But, before that, put whatever present in cooldown
// or previous back to PQ as its cooldown is done.
if (previous != null && previous.getValue() > 0) {
pq.offer(previous);
}
polled.setValue(polled.getValue() - 1);
previous = polled;
}
// step 6: at this moment, we should have used
// all chars and previous should be null. Else, not possible
// Example: "aaab"
// For this, heap becomes empty, but previous still has {a:1}
if (previous != null && previous.getValue() > 0) {
return "";
}
return sb.toString();
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.reorganizeString("aab").equals("aba"));
System.out.println(s.reorganizeString("aaab").equals(""));
}
}
🔑 Key Insights:
- Why Greedy?: Most frequent hardest to separate, place first!
- Why Max-Heap?: Always pick most frequent available
- Cooldown: Previous can't be used immediately (adjacent constraint)
- Impossibility: maxFreq > (n+1)/2 → need (maxFreq-1) gaps, have (n-maxFreq) others
- Why (n+1)/2?: Handles even (n/2) and odd ((n+1)/2) uniformly
- Early Check: Save time on impossible cases
- Time: O(n log k), k ≤ 26, Space: O(k) ✓
🎪 Memory Aid:
"Most frequent first, spreads them out!"
"Cooldown = can't reuse just placed!"
"Max > (n+1)/2? Impossible!" ✨
🧪 Edge Cases
Case 1: All same character
s = "aaaa", n=4
maxFreq = 4
4 > (4+1)/2 = 2.5? YES
Impossible → ""
Case 2: All different
s = "abcd", n=4
maxFreq = 1
1 > 2.5? NO
Possible → "abcd" (or any order)
Case 3: Exactly at threshold
s = "aabbc", n=5
maxFreq = 2
2 > 3? NO
Possible → "abcab" ✓
All handled correctly! ✓
🎓 Complexity Analysis
Both Approaches
Time: O(n log k)
Count frequencies: O(n)
Build heap: O(k log k) ≤ O(26 log 26) = O(1)
Greedy construction: O(n log k)
n iterations
Each: poll O(log k) + offer O(log k)
k ≤ 26 (lowercase letters)
So effectively O(n)!
Space: O(k)
Frequency map: O(k)
Heap: O(k)
k ≤ 26, so O(1)!
Optimal!
Happy practicing! 🎯
Note: This problem beautifully demonstrates GREEDY optimization with mathematical impossibility checking! You learn: (1) WHY greedy works (most frequent first spreads them out), (2) WHY the formula maxFreq > (n+1)/2 determines impossibility (need gaps to separate), (3) Cooldown mechanism (can't reuse just-placed), (4) Connection to Task Scheduler. The proof that greedy is optimal, the derivation of the impossibility formula from first principles, and understanding when (n+1)/2 vs n/2 matters builds deep algorithmic intuition! This pattern appears in many scheduling/rearrangement problems! True mastery! 💪✨🏆