Longest Happy String

A string s is called happy if it satisfies the following conditions:

1405. Longest Happy String

Difficulty: Medium

Link: LeetCode Problem

Problem Statement

A string s is called happy if it follows all these rules:

• s only has the letters 'a', 'b', and 'c'.
• s does not contain "aaa", "bbb", or "ccc" as a substring.
• s has at most a copies of the letter 'a'.
• s has at most b copies of the letter 'b'.
• s has at most c copies of the letter 'c'.

You are given three numbers: a, b, and c.

Return the longest possible happy string. If more than one longest string works, you can return any one of them. If no happy string can be made, return an empty string "".

A substring means letters that sit next to each other in the string, in order.

Examples

Example 1

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"

Another correct answer would be "ccbccacc".

Example 2

Input: a = 7, b = 1, c = 0
Output: "aabaa"

This is the only correct answer for this case.

Solution

The steps to solve this problem:

• We create a max heap. We push each letter into the heap along with how many times it can still be used.
• We pop the letter with the highest remaining count from the heap.
• Before adding it to our result, we check: would this letter appear three times in a row? We check the last two letters already in our result.
  • If it does not create three in a row, we add the letter to the result. We reduce its count by 1, and push it back into the heap if its count is still more than 0.
  • If it would create three in a row, we cannot use it right now. So:
    • If the heap is empty, there is no other letter to use. We stop here.
    • If the heap is not empty, we pop the next-highest letter instead. We add that letter to the result, reduce its count, and push it back if needed.
    • We also push the first letter (the one we skipped) back into the heap, unused, so we can try it again later.
• We repeat this process until the heap is empty.

Code

class MaxHeap {
  constructor(comparator) {
    this.heap = [];
    this.comparator = comparator;
  }

  size() { return this.heap.length; }
  isEmpty() { return this.heap.length === 0; }
  peek() { return this.heap[0]; }

  push(val) {
    this.heap.push(val);
    this._bubbleUp(this.heap.length - 1);
  }

  pop() {
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._bubbleDown(0);
    }
    return top;
  }

  _bubbleUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.comparator(this.heap[parent], this.heap[i]) >= 0) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  _bubbleDown(i) {
    const n = this.heap.length;
    while (true) {
      const left = 2 * i + 1, right = 2 * i + 2;
      let best = i;
      if (left < n && this.comparator(this.heap[left], this.heap[best]) > 0) best = left;
      if (right < n && this.comparator(this.heap[right], this.heap[best]) > 0) best = right;
      if (best === i) break;
      [this.heap[i], this.heap[best]] = [this.heap[best], this.heap[i]];
      i = best;
    }
  }
}

var longestDiverseString = function(a, b, c) {
  const heap = new MaxHeap((x, y) => x[0] - y[0]); // compare by count

  if (a > 0) heap.push([a, 'a']);
  if (b > 0) heap.push([b, 'b']);
  if (c > 0) heap.push([c, 'c']);

  let result = [];

  while (!heap.isEmpty()) {
    const [count, letter] = heap.pop();
    const len = result.length;

    // Check if using this letter would create three-in-a-row
    if (len >= 2 && result[len - 1] === letter && result[len - 2] === letter) {
      // Can't use this letter right now — try the next-highest instead
      if (heap.isEmpty()) break; // no alternative letter available, must stop

      const [count2, letter2] = heap.pop();
      result.push(letter2);
      if (count2 - 1 > 0) heap.push([count2 - 1, letter2]);

      // put the original letter back, unused, for next round
      heap.push([count, letter]);
    } else {
      result.push(letter);
      if (count - 1 > 0) heap.push([count - 1, letter]);
    }
  }

  return result.join('');
};