Given a string, rearrange it so that any two adjacent characters are not the same. If such a reorganization of the characters is possible, output any possible valid arrangement. Otherwise, return an empty string.

1-reorganize-string.js

export function reorganizeString(inputString) {
  // build a hash map where keys are characters, and values are their frequencies
  const map = {};
  for (let i = 0; i < inputString.length; ++i) {
    const char = inputString[i];
    map[char] = (map[char] ?? 0) + 1;
  }

  // initialize max heap by pushing character frequencies together with characters
  // so heap will always contain a character with max frequency value on top
  const uniqueChars = Object.keys(map);
  const heap = new MaxHeap();
  for (let i = 0; i < uniqueChars.length; ++i) {
    const char = uniqueChars[i];
    heap.offer([map[char], char]);
  }

  // store final result here
  let result = "";
  // store character we've just added to the result string here, with frequency
  // since we pop it from the heap, we don't add it to the heap right away
  // in order to avoid same adjacent characters in case some character frequency is much higher than the other
  let added = null;

  while (heap.size() > 0) {
    // remove character with max frequency from heap
    const [freq, char] = heap.poll();
    // add it to string
    result += char;

    // if we have a character that we've added on the previous step,
    // add it to the heap now
    if (added !== null) {
      heap.offer(added);
    }

    // calculate new frequency of the character we added at this step
    const newFreq = freq - 1;
    if (newFreq > 0) {
      // if new frequency is >0, save it to variable
      added = [newFreq, char];
    } else {
      // otherwise reset variable
      added = null;
    }
  }

  // this variable being not null means we could not re-add all characters in a way that is required
  if (added !== null) {
    return "";
  }

  return result;
}

2-README.md