Reorganize String
Mahabharata — The Alternating Formation — Arrange Warriors So No Two Identical Are Adjacent
एक ही योद्धा — पास-पास नहीं। सबसे अधिक वाला पहले — फिर दूसरा — बारी-बारी॥
*Same warrior — not side by side. Most frequent first — then second — alternating.*
The Story
Rearrange a string so no two adjacent characters are the same. Return "" if impossible.
For `s="aab"`: return "aba". For `s="aaab"`: return "" (impossible, 3 a's can't be separated in 4 chars).
**Impossibility check:** If max_frequency > ceil(n/2), it's impossible.
**Max-Heap Greedy:** - Max-heap of [char, freq] pairs ordered by freq - At each step: pop the most frequent char that is DIFFERENT from the last added char - If different: add it, push back with freq-1 - If same as last (or heap has only that char): pop the second most frequent instead
Simpler two-pointer approach: - Count frequencies. Find most frequent char. - Place at even indices (0,2,4,...) first, then fill odd indices with remaining chars.
```java int[] freq = new int[26]; for (char c : s.toCharArray()) freq[c-'a']++; int maxIdx=0; for (int i=1;i<26;i++) if (freq[i]>freq[maxIdx]) maxIdx=i; if (freq[maxIdx]>(s.length()+1)/2) return ""; // Impossible char[] res = new char[s.length()]; int idx=0; // Place most frequent at even indices while (freq[maxIdx] > 0) { res[idx]=(char)('a'+maxIdx); idx+=2; freq[maxIdx]--; } // Fill remaining for (int i=0;i<26;i++) while (freq[i]>0) { if (idx >= s.length()) idx=1; res[idx]=(char)('a'+i); idx+=2; freq[i]--; } return new String(res); ```
The heap approach: ```java PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->b[1]-a[1]); for (int i=0;i<26;i++) if (freq[i]>0) pq.offer(new int[]{i,freq[i]}); StringBuilder sb = new StringBuilder(); while (!pq.isEmpty()) { int[] top = pq.poll(); if (sb.length()>0 && sb.charAt(sb.length()-1)==(char)('a'+top[0])) { if (pq.isEmpty()) return ""; // Only same char left int[] second = pq.poll(); sb.append((char)('a'+second[0])); if (--second[1]>0) pq.offer(second); pq.offer(top); } else { sb.append((char)('a'+top[0])); if (--top[1]>0) pq.offer(top); } } return sb.toString(); ```
The Backtracking Arranger
Try all permutations, check adjacency. O(n!). Infeasible for large n.
// Backtracking — infeasible for large n
// Use the placement-at-even-indices approach instead:
public String reorganizeStringPlacement(String s) {
int[] freq = new int[26];
for (char c : s.toCharArray()) freq[c-'a']++;
int maxIdx=0;
for (int i=1;i<26;i++) if (freq[i]>freq[maxIdx]) maxIdx=i;
if (freq[maxIdx]>(s.length()+1)/2) return "";
char[] res = new char[s.length()];
int idx=0;
while (freq[maxIdx]>0){res[idx]=(char)('a'+maxIdx);idx+=2;freq[maxIdx]--;}
for (int i=0;i<26;i++) while(freq[i]>0){
if(idx>=s.length())idx=1;
res[idx]=(char)('a'+i);idx+=2;freq[i]--;}
return new String(res);
}The Most-Frequent-First Heap Wisdom
public String reorganizeString(String s) {
int[] freq = new int[26];
for (char c : s.toCharArray()) freq[c - 'a']++;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[1] - a[1]);
for (int i = 0; i < 26; i++) if (freq[i] > 0) pq.offer(new int[]{i, freq[i]});
StringBuilder sb = new StringBuilder();
while (!pq.isEmpty()) {
int[] top = pq.poll();
if (sb.length() > 0 && sb.charAt(sb.length()-1) == (char)('a' + top[0])) {
if (pq.isEmpty()) return "";
int[] second = pq.poll();
sb.append((char)('a' + second[0]));
if (--second[1] > 0) pq.offer(second);
pq.offer(top);
} else {
sb.append((char)('a' + top[0]));
if (--top[1] > 0) pq.offer(top);
}
}
return sb.toString();
}Step-by-Step Walkthrough
s="ab"
freq: a=1,b=1. pq=[('a',1),('b',1)] (or ('b',1),('a',1) by lex tie)
Step1: append either, say 'a'. sb="a"
Step2: poll 'b'(1). last='a' diff → append 'b'. sb="ab" ✅Deep Insight
**The even-index placement trick:** A more elegant O(n) solution: 1. Find the most frequent character 2. Check feasibility: freq_max ≤ ceil(n/2) 3. Place it at indices 0, 2, 4, ... 4. Fill remaining characters at remaining indices (continuing from odd indices after exhausting even) This guarantees no adjacency violations for the most frequent char.
**Why feasibility check is freq_max ≤ (n+1)/2?** In a string of length n, there are ceil(n/2) even positions. The most frequent char must fit in those positions alone (when it's the bottleneck).
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n log 26) = O(n) | O(26) = O(1) | Placement at even indices |
| Optimal | O(n log 26) = O(n) | O(26) = O(1) | Heap bounded by 26 chars |
Pattern Recognition
✅ No adjacent duplicates → max-heap greedy ✅ Impossible if maxFreq > (n+1)/2 ✅ Always place most frequent (if different from last) ✅ Alternative: even-index placement for most frequent **LeetCode Trigger Phrases:** → "reorganize string" no adjacent repeats → Interleave by frequency → Related: task scheduler (hp-11)
Bhagavad Gita 15.5
द्वन्द्वैर्विमुक्ताः सुखदुःखसंज्ञैर्गच्छन्त्यमूढाः पदमव्ययं तत्।
Free from the pairs of opposites — free from joy and grief — the undeluded reach that imperishable state.
Connection: The reorganized string must alternate — no character standing next to its identical twin. Like the sage's freedom from duality (neither too much of one thing, nor its exclusion), the algorithm creates balance by ensuring no character dominates consecutive positions. The most frequent character, placed at alternating even positions, achieves this equanimity — maximum presence without undue clustering.