MaiDeveloper

Reorganize String

Given a string str, check if the letters can be rearranged so that two characters that are adjacent to each other are not the same.

If possible, output any possible result. If not possible, return the empty string.

Example 1:

Input: str = "aab"
Output: "aba"

Example 2:

Input: str = "aaab"
Output: ""

Solution


/**
 * @param {string} str
 * @return {string}
 * @time complexity: O(N log A), N is the length of str and A is the size of the alphabet
 * @space complexity: O(A)
 */
var reorganizeString = function(str) {
  const count = {};
  const maxHeap = new BinaryHeap((a, b) => b.count - a.count);
  let ans = '';
  let lastChar = '';

  // Count the number of times each character appears
  for (let char of str) {
    count[char] = (count[char] || 0) + 1;
  }

  for (let k in count) {
    // If a character appears more than half the string
    // It is not possible to reorganize the string
    if (count[k] > Math.ceil(str.length / 2)) {
      return '';
    }
    // Add to the heap
    maxHeap.insert({
      count: count[k],
      char: k
    });
  }

  while (maxHeap.size() >= 2) {
    const a = maxHeap.extract();
    const b = maxHeap.extract();

    // Make sure the character we are about to added to the ans
    // are not the same as the last character
    if (a.char === lastChar) {
      ans += b.char + a.char;
      lastChar = a.char;
    } else {
      ans += a.char + b.char;
      lastChar = b.char;
    }

    a.count--;
    b.count--;

    if (a.count > 0) {
      maxHeap.insert(a);
    }
    if (b.count > 0) {
      maxHeap.insert(b);
    }
  }

  if (maxHeap.size() > 0) {
    ans += maxHeap.extract().char;
  }

  return ans;
};

class BinaryHeap {
  constructor(comparator = (a, b) => {
    return (a < b) ? -1 : (a === b ? 0 : 1);
  }) {
    this.heap = [];
    this.comparator = comparator;
  }
  getLeftIndex(index) {
    return 2 * index + 1;
  }
  getRightIndex(index) {
    return 2 * index + 2;
  }
  getParentIndex(index) {
    return Math.floor((index - 1) / 2);
  }
  insert(data) {
    if (data === undefined || data === null) {
      return false;
    }
    this.heap.push(data);
    this.bubbleUp(this.heap.length - 1);
    return true;
  }
  bubbleUp(index) {    
    while (index > 0) {
      let curr = this.heap[index];
      let parentIndex = this.getParentIndex(index);
      let parent = this.heap[parentIndex];
      
      let compare = this.comparator(parent, curr);
      if (compare < 0 || compare === 0) {
        break;
      }
      
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }
  extract() {
    if (this.size() === 0) {
      return undefined;
    }
    
    if (this.size() === 1) {
      return this.heap.shift();
    }
    
    const value = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.sinkDown(0);
    return value;
  }
  sinkDown(currIndex) {
    let left = this.getLeftIndex(currIndex);
    let right = this.getRightIndex(currIndex);
    let parentIndex = currIndex;
    
    if (left < this.size() && this.comparator(this.heap[left], this.heap[parentIndex]) < 0) {
      parentIndex = left;
    }
    
    if (right < this.size() && this.comparator(this.heap[right], this.heap[parentIndex]) < 0) {
      parentIndex = right;
    }
    
    if (parentIndex !== currIndex) {
      this.swap(parentIndex, currIndex);
      this.sinkDown(parentIndex);
    }
  }
  peak() {
    return this.size() > 0 ? this.heap[0] : undefined;
  }
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
  size() {
    return this.heap.length;
  }
}

Test Case

describe('Reorganize String', () => {
  it("should return 'aba' if 'aab' is given", () => {
    assert.equal(reorganizeString('aab'), 'aba');
  });
  it("should return '' if 'aaab' is given", () => {
    assert.equal(reorganizeString('aaab'), '');
  });
});
  Reorganize String
    ✓ should return 'aba' if 'aab' is given
    ✓ should return '' if 'aaab' is given


  2 passing (11ms)


Mike Mai
Mike Mai   Brooklyn, New York
I am full-stack web developer, passionate about building world class web applications. Knowledge in designing, coding, testing, and debugging. I love to solve problems.