Reorganize String

class Solution {
public:
    string reorganizeString(string s) {
        int cnt[26] = {0};
        for (char c : s) ++cnt[c - 'a'];
        int maxFreq = *max_element(cnt, cnt + 26);
        if (maxFreq > (int)(s.size() + 1) / 2) return "";
        priority_queue<pair<int,char>> pq;
        for (int i = 0; i < 26; ++i) if (cnt[i]) pq.push({cnt[i], 'a' + i});
        string out;
        while (pq.size() >= 2) {
            auto [c1, ch1] = pq.top(); pq.pop();
            auto [c2, ch2] = pq.top(); pq.pop();
            out += ch1;
            out += ch2;
            if (--c1) pq.push({c1, ch1});
            if (--c2) pq.push({c2, ch2});
        }
        if (!pq.empty()) out += pq.top().second;
        return out;
    }
};

import "container/heap"

type rItem struct {
    cnt int
    ch  byte
}
type rHeap []rItem

func (h rHeap) Len() int            { return len(h) }
func (h rHeap) Less(i, j int) bool  { return h[i].cnt > h[j].cnt }
func (h rHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *rHeap) Push(x interface{}) { *h = append(*h, x.(rItem)) }
func (h *rHeap) Pop() interface{}   { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

func reorganizeString(s string) string {
    var cnt [26]int
    for i := 0; i < len(s); i++ {
        cnt[s[i]-'a']++
    }
    maxFreq := 0
    for _, c := range cnt {
        if c > maxFreq {
            maxFreq = c
        }
    }
    if maxFreq > (len(s)+1)/2 {
        return ""
    }
    pq := &rHeap{}
    heap.Init(pq)
    for i := 0; i < 26; i++ {
        if cnt[i] > 0 {
            heap.Push(pq, rItem{cnt[i], byte('a' + i)})
        }
    }
    out := []byte{}
    for pq.Len() >= 2 {
        a := heap.Pop(pq).(rItem)
        b := heap.Pop(pq).(rItem)
        out = append(out, a.ch, b.ch)
        if a.cnt-1 > 0 {
            heap.Push(pq, rItem{a.cnt - 1, a.ch})
        }
        if b.cnt-1 > 0 {
            heap.Push(pq, rItem{b.cnt - 1, b.ch})
        }
    }
    if pq.Len() > 0 {
        out = append(out, (*pq)[0].ch)
    }
    return string(out)
}

import heapq
from collections import Counter

class Solution:
    def reorganizeString(self, s: str) -> str:
        cnt = Counter(s)
        if max(cnt.values()) > (len(s) + 1) // 2:
            return ""
        # Max-heap via negated counts.
        pq: list[tuple[int, str]] = [(-c, ch) for ch, c in cnt.items()]
        heapq.heapify(pq)
        out: list[str] = []
        while len(pq) >= 2:
            c1, ch1 = heapq.heappop(pq)
            c2, ch2 = heapq.heappop(pq)
            out.append(ch1)
            out.append(ch2)
            if c1 + 1 < 0:
                heapq.heappush(pq, (c1 + 1, ch1))
            if c2 + 1 < 0:
                heapq.heappush(pq, (c2 + 1, ch2))
        if pq:
            out.append(pq[0][1])
        return ''.join(out)

class MaxHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    push(x) {
        this.h.push(x);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] >= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let best = i;
                if (l < n && this.h[l][0] > this.h[best][0]) best = l;
                if (r < n && this.h[r][0] > this.h[best][0]) best = r;
                if (best === i) break;
                [this.h[best], this.h[i]] = [this.h[i], this.h[best]];
                i = best;
            }
        }
        return top;
    }
    top() { return this.h[0]; }
}

function reorganizeString(s) {
    const cnt = new Array(26).fill(0);
    const A = 'a'.charCodeAt(0);
    for (const c of s) cnt[c.charCodeAt(0) - A]++;
    let maxFreq = 0;
    for (const c of cnt) if (c > maxFreq) maxFreq = c;
    if (maxFreq > ((s.length + 1) >> 1)) return '';
    const pq = new MaxHeap();
    for (let i = 0; i < 26; i++) {
        if (cnt[i]) pq.push([cnt[i], String.fromCharCode(A + i)]);
    }
    const out = [];
    while (pq.size() >= 2) {
        const [c1, ch1] = pq.pop();
        const [c2, ch2] = pq.pop();
        out.push(ch1, ch2);
        if (c1 - 1 > 0) pq.push([c1 - 1, ch1]);
        if (c2 - 1 > 0) pq.push([c2 - 1, ch2]);
    }
    if (pq.size()) out.push(pq.top()[1]);
    return out.join('');
}

class Solution {
    public String reorganizeString(String s) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;
        int maxFreq = 0;
        for (int c : cnt) maxFreq = Math.max(maxFreq, c);
        if (maxFreq > (s.length() + 1) / 2) return "";
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        for (int i = 0; i < 26; i++) {
            if (cnt[i] > 0) pq.offer(new int[]{cnt[i], i});
        }
        StringBuilder out = new StringBuilder();
        while (pq.size() >= 2) {
            int[] a = pq.poll();
            int[] b = pq.poll();
            out.append((char) ('a' + a[1]));
            out.append((char) ('a' + b[1]));
            if (--a[0] > 0) pq.offer(a);
            if (--b[0] > 0) pq.offer(b);
        }
        if (!pq.isEmpty()) out.append((char) ('a' + pq.peek()[1]));
        return out.toString();
    }
}

class MaxHeap {
    private h: Array<[number, string]> = [];
    size(): number { return this.h.length; }
    push(x: [number, string]): void {
        this.h.push(x);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] >= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): [number, string] {
        const top = this.h[0];
        const last = this.h.pop() as [number, string];
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1;
                const r = 2 * i + 2;
                let best = i;
                if (l < n && this.h[l][0] > this.h[best][0]) best = l;
                if (r < n && this.h[r][0] > this.h[best][0]) best = r;
                if (best === i) break;
                [this.h[best], this.h[i]] = [this.h[i], this.h[best]];
                i = best;
            }
        }
        return top;
    }
    top(): [number, string] { return this.h[0]; }
}

function reorganizeString(s: string): string {
    const cnt: number[] = new Array<number>(26).fill(0);
    const A = 'a'.charCodeAt(0);
    for (const c of s) cnt[c.charCodeAt(0) - A]++;
    let maxFreq = 0;
    for (const c of cnt) if (c > maxFreq) maxFreq = c;
    if (maxFreq > ((s.length + 1) >> 1)) return '';
    const pq = new MaxHeap();
    for (let i = 0; i < 26; i++) {
        if (cnt[i]) pq.push([cnt[i], String.fromCharCode(A + i)]);
    }
    const out: string[] = [];
    while (pq.size() >= 2) {
        const [c1, ch1] = pq.pop();
        const [c2, ch2] = pq.pop();
        out.push(ch1, ch2);
        if (c1 - 1 > 0) pq.push([c1 - 1, ch1]);
        if (c2 - 1 > 0) pq.push([c2 - 1, ch2]);
    }
    if (pq.size()) out.push(pq.top()[1]);
    return out.join('');
}