1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
/**
 * Frequency Count and Check Approach
 * Time Complexity: O(n) - Where n is the length of the string
 * Space Complexity: O(1) - Since we only use a fixed-size array for frequency counts
 *
 * @param {string} s - The input string
 * @return {string} - The reorganized string or an empty string if not possible
 */
function reorganizeString(s) {
  // Count the frequency of each character
  const freq = new Array(26).fill(0);
  for (const c of s) {
    freq[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
  }
 
  // Find the maximum frequency and the corresponding character
  let maxFreq = 0;
  let maxChar = 0;
  for (let i = 0; i < 26; i++) {
    if (freq[i] > maxFreq) {
      maxFreq = freq[i];
      maxChar = i;
    }
  }
 
  // Check if a valid rearrangement is possible
  if (maxFreq > Math.floor((s.length + 1) / 2)) {
    return "";
  }
 
  // Create an array to store the result
  const result = new Array(s.length);
  let index = 0;
 
  // Place the most frequent character at even positions
  while (freq[maxChar] > 0) {
    result[index] = String.fromCharCode(maxChar + 'a'.charCodeAt(0));
    index += 2;
    freq[maxChar]--;
  }
 
  // Place the remaining characters
  for (let i = 0; i < 26; i++) {
    while (freq[i] > 0) {
      // If we've filled all even positions, switch to odd positions
      if (index >= s.length) {
        index = 1;
      }
 
      result[index] = String.fromCharCode(i + 'a'.charCodeAt(0));
      index += 2;
      freq[i]--;
    }
  }
 
  return result.join('');
}
 
/**
 * Max Heap Approach
 * Time Complexity: O(n log k) - Where n is the length of the string and k is the number of unique characters
 * Space Complexity: O(k) - For the heap and frequency map
 *
 * @param {string} s - The input string
 * @return {string} - The reorganized string or an empty string if not possible
 */
function reorganizeStringMaxHeap(s) {
  // Count the frequency of each character
  const freqMap = new Map();
  for (const c of s) {
    freqMap.set(c, (freqMap.get(c) || 0) + 1);
  }
 
  // Check if a valid rearrangement is possible
  const maxFreq = Math.max(...freqMap.values());
  if (maxFreq > Math.floor((s.length + 1) / 2)) {
    return "";
  }
 
  // Create a max heap of [frequency, character] pairs
  const heap = new MaxHeap();
  for (const [char, freq] of freqMap.entries()) {
    heap.add([freq, char]);
  }
 
  // Construct the result string
  let result = "";
  let prev = null; // Character set aside from the previous iteration
 
  while (heap.size() > 0 || prev) {
    // If the heap is empty but we still have a previous character, it's impossible
    if (heap.size() === 0 && prev) {
      return "";
    }
 
    // Extract the most frequent character
    const [freq, char] = heap.poll();
    result += char;
 
    // Add the previous character back to the heap if it has remaining occurrences
    if (prev) {
      heap.add(prev);
      prev = null;
    }
 
    // Set aside the current character if it has remaining occurrences
    if (freq > 1) {
      prev = [freq - 1, char];
    }
  }
 
  return result;
}
 
/**
 * Max Heap implementation
 */
class MaxHeap {
  constructor() {
    this.heap = [];
  }
 
  size() {
    return this.heap.length;
  }
 
  add(val) {
    this.heap.push(val);
    this.siftUp(this.heap.length - 1);
  }
 
  poll() {
    if (this.size() === 0) {
      return null;
    }
 
    const max = this.heap[0];
    const last = this.heap.pop();
 
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.siftDown(0);
    }
 
    return max;
  }
 
  siftUp(index) {
    let parent = Math.floor((index - 1) / 2);
 
    while (index > 0 && this.heap[parent][0] < this.heap[index][0]) {
      [this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
      index = parent;
      parent = Math.floor((index - 1) / 2);
    }
  }
 
  siftDown(index) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let largest = index;
 
    if (left < this.heap.length && this.heap[left][0] > this.heap[largest][0]) {
      largest = left;
    }
 
    if (right < this.heap.length && this.heap[right][0] > this.heap[largest][0]) {
      largest = right;
    }
 
    if (largest !== index) {
      [this.heap[index], this.heap[largest]] = [this.heap[largest], this.heap[index]];
      this.siftDown(largest);
    }
  }
}
 
/**
 * Alternating Positions Approach
 * Time Complexity: O(n) - Where n is the length of the string
 * Space Complexity: O(n) - For the result array
 *
 * @param {string} s - The input string
 * @return {string} - The reorganized string or an empty string if not possible
 */
function reorganizeStringAlternating(s) {
  // Count the frequency of each character
  const freq = new Array(26).fill(0);
  for (const c of s) {
    freq[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
  }
 
  // Find the maximum frequency
  let maxFreq = 0;
  for (let i = 0; i < 26; i++) {
    maxFreq = Math.max(maxFreq, freq[i]);
  }
 
  // Check if a valid rearrangement is possible
  if (maxFreq > Math.floor((s.length + 1) / 2)) {
    return "";
  }
 
  // Create an array to store the result
  const result = new Array(s.length);
 
  // Sort characters by frequency (most frequent first)
  const charFreq = [];
  for (let i = 0; i < 26; i++) {
    if (freq[i] > 0) {
      charFreq.push([freq[i], i]);
    }
  }
  charFreq.sort((a, b) => b[0] - a[0]);
 
  // Place characters at alternating positions
  let index = 0;
 
  for (const [count, char] of charFreq) {
    const c = String.fromCharCode(char + 'a'.charCodeAt(0));
 
    for (let i = 0; i < count; i++) {
      // If we've filled all even positions, switch to odd positions
      if (index >= s.length) {
        index = 1;
      }
 
      result[index] = c;
      index += 2;
    }
  }
 
  return result.join('');
}