Longest Happy String

Description

A string is called happy if it does not have any of the strings 'aaa', 'bbb' or 'ccc' as a substring.

Given three integers a, b and c, return any string s, which satisfies following conditions:

• s is happy and longest possible.
• s contains at most a occurrences of the letter 'a', at most b occurrences of the letter 'b' and at most c occurrences of the letter 'c'.
• s will only contain 'a', 'b' and 'c' letters.

If there is no such string s return the empty string "".

 

Example 1:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 2, b = 2, c = 1
Output: "aabbc"

Example 3:

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It's the only correct answer in this case.

 

Constraints:

• 0 <= a, b, c <= 100
• a + b + c > 0

Solution(javascript)

/** Greedy
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {string}
 */
const longestDiverseString = function (a, b, c) {
  const map = {
    a,
    b,
    c,
  }
  const sort = () => Object.keys(map).sort((key1, key2) => map[key2] - map[key1])
  let s = ''
  const addKey = (key) => {
    if (map[key] > 1) {
      map[key] -= 2
      s += key + key
    } else if (map[key] === 1) {
      map[key] -= 1
      s += key
    }
  }
  while (map.a > 0 || map.b > 0 || map.c > 0) {
    const [key1, key2] = sort()
    if (map[key2] === 0) {
      addKey(key1)
      return s
    }
    if (map[key1] / map[key2] >= 2) {
      map[key1] -= 2
      s += key1 + key1
      map[key2] -= 1
      s += key2
    } else {
      addKey(key1)
      addKey(key2)
    }
  }

  return s
}