🥈1405. 最长快乐字符串

如果字符串中不含有任何 aaa，bbb 或 ccc 这样的字符串作为子串，那么该字符串就是一个快乐字符串。

给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：

1. s 是一个尽可能长的快乐字符串。
2. s中 最多有a 个字母 a、b个字母 b、c个字母 c。
3. s中只含有a、b 、c三种字母。

如果不存在这样的字符串 s ，请返回一个空字符串 “”。

示例 1：

输入：a = 1, b = 1, c = 7
输出："ccaccbcc"
解释："ccbccacc" 也是一种正确答案。

示例 2：

输入：a = 2, b = 2, c = 1
输出："aabbc"

示例 3：

输入：a = 7, b = 1, c = 0
输出："aabaa"
解释：这是该测试用例的唯一正确答案。

提示：

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

题解

好久没有刷过题了，自然懵逼😳，慢慢理解吧。

贪心

题目要求最长的快乐字符串，且快乐字符串中不能有三个连续的字母，可以用如下贪心策略：

• 每次优先安排剩余最多的字母，假如最多的字母前边已经达到连续两个了，那么就安排第二多的字母
• 如果所有的字母都无法添加，就直接退出，此时构成的字符串就是最长的快乐字符串。

复杂度分析

• 时间复杂度： ， 其中、、为给定的整数，为字母种类，每次从待选的字母中选择一个字母需要排序一次时间复杂度为为，最多需要选择个字母
• 空间复杂度：， 为字母种类

JavaScript

var longestDiverseString = function (a, b, c) {
  const abc = [['a', a], ['b', b], ['c', c]];
  let res = '';
  while (true) {
    abc.sort((a, b) => b[1] - a[1]);
    //如果字符串最后两个字符和数目最多的字母都相同，就该用第二多的字母了
    const idx = res.slice(-2) === abc[0][0].repeat(2) ? 1 : 0;
    // 如果第二多字母为0，就要输出字符串
    if (abc[idx][1]-- === 0) {
      return res
    };
    res += abc[idx][0];
  }
};