export function reorganizeString(s: string): string {
  const freq = new Map<string, number>();

  for (const char of s) {
    freq.set(char, (freq.get(char) ?? 0) + 1);
  }

  const maxFreq = Math.max(...freq.values());

  if (maxFreq > Math.ceil(s.length / 2)) {
    return '';
  }

  const heap: [string, number][] = [...freq.entries()];

  const heapifyUp = (index: number) => {
    while (index > 0) {
      const parent = Math.floor((index - 1) / 2);

      if (heap[parent][1] >= heap[index][1]) {
        break;
      }

      [heap[parent], heap[index]] = [heap[index], heap[parent]];
      index = parent;
    }
  };

  const heapifyDown = (index: number) => {
    while (true) {
      let largest = index;

      const left = index * 2 + 1;
      const right = index * 2 + 2;

      if (
        left < heap.length &&
        heap[left][1] > heap[largest][1]
      ) {
        largest = left;
      }

      if (
        right < heap.length &&
        heap[right][1] > heap[largest][1]
      ) {
        largest = right;
      }

      if (largest === index) {
        break;
      }

      [heap[index], heap[largest]] = [heap[largest], heap[index]];
      index = largest;
    }
  };

  const push = (item: [string, number]) => {
    heap.push(item);
    heapifyUp(heap.length - 1);
  };

  const pop = (): [string, number] | undefined => {
    if (heap.length === 0) return undefined;

    if (heap.length === 1) {
      return heap.pop();
    }

    const max = heap[0];
    heap[0] = heap.pop()!;
    heapifyDown(0);

    return max;
  };

  for (let i = Math.floor(heap.length / 2) - 1; i >= 0; i--) {
    heapifyDown(i);
  }

  let result = '';
  let previous: [string, number] | null = null;

  while (heap.length > 0) {
    const current = pop()!;

    result += current[0];

    current[1]--;

    if (previous && previous[1] > 0) {
      push(previous);
    }

    previous = current;
  }

  return result.length === s.length ? result : '';
}