767. Reorganize String
Tags:
Medium
Skills:
QueueHeap
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Approach
Time and space complexity:
Solution - MaxPriorityQueue
1function reorganizeString(s: string): string {
2 const char_count: Record<string, number> = {};
3 for (const char of s) {
4 char_count[char] = (char_count[char] || 0) + 1;
5 }
6
7 const max_freq = Math.max(...Object.values(char_count));
8 if (max_freq > Math.ceil(s.length / 2)) {
9 return "";
10 }
11
12 const max_heap = new MaxPriorityQueue((entry: { char: string; freq: number }) => entry.freq);
13
14 for (const [char, freq] of Object.entries(char_count)) {
15 max_heap.enqueue({ char, freq });
16 }
17
18 const result: string[] = [];
19
20 while (max_heap.size() > 1) {
21 const first = max_heap.dequeue();
22 const second = max_heap.dequeue();
23
24 result.push(first?.char);
25 result.push(second?.char);
26
27 if (first?.freq - 1 > 0) {
28 max_heap.enqueue({ char: first.char, freq: first.freq - 1 });
29 }
30 if (second?.freq - 1 > 0) {
31 max_heap.enqueue({ char: second.char, freq: second.freq - 1 });
32 }
33 }
34
35 if (!max_heap.isEmpty()) {
36 const last = max_heap.dequeue();
37 if (last.freq > 1) return "";
38 result.push(last.char);
39 }
40
41 return result.join("");
42}
43