跳到主要内容

1405.最长快乐字符串

· 阅读需 5 分钟

1、题干​

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

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

  • s 是一个尽可能长的快乐字符串。
  • s 中 最多 有a 个字母 'a'、b 个字母 'b'、c 个字母 'c' 。
  • 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

题目对我来说挺有难度，想了蛮久，用了两种思路，都是基于3种字母的数量关系解题，这里记录其中一种

e9de6ffd302988140f868f8f54c96d26.gif


2、解题思路​

总体思路

  • 按数量对 'a'、'b' 、'c' 三种字母进行降序排序
  • 由于快乐字符串中不能出现3个连续相同字符，可以先取数量最多的字母，每两个组成一个字符串并存入数组中，记为 arr
  • 遍历 arr 中的所有字符串，把剩余字母逐个拼接到每个字符串末尾，由于剩余任意一种字母数量都不会超过 2∗arr.length2*arr.length，因此任意一种字母必定可以在两轮循环内消耗完，且 arr 中任意一个字符串都不会出现3个连续相同字符
  • 最后拼接所有字符串，只可能在末尾出现3个以上连续相同字符，把末尾多余字符处理掉即可

举个例子 ：a = 1, b = 1, c = 7

  • 1、取数量最多的字母 c，每两个组成一个字符串，得到：['cc','cc','cc','c']
  • 2、把剩余字母 a 逐个拼接到每个字符串末尾，得到：['cca','cc','cc','c']，此时一轮循环尚未结束
  • 3、一轮循环没结束，字母 a 已耗尽，继续该轮循环，把剩余字母 b 逐个拼接到每个字符串末尾，得到：['cca','ccb','cc','c']
  • 4、拼接所有字符串再处理末尾多余字符，得到：'ccaccbcc'

再举个例子 ：a = 6, b = 6, c = 6

  • 1、取数量最多的字母 a，每两个组成一个字符串，得到：['aa','aa','aa']
  • 2、把剩余字母 b 逐个拼接到每个字符串末尾，得到：['aab','aab','aab']，此时已结束一轮循环
  • 3、一轮循环没有消耗所有字母 b，再来一轮，得到：['aabb','aabb','aabb']，此时已结束两轮循环
  • 4、同理把剩余字母 c 逐个拼接到每个字符串末尾，得到：['aabbcc','aabbcc','aabbcc']
  • 5、拼接所有字符串再处理末尾多余字符，得到：'aabbccaabbccaabbcc

3、代码​

var longestDiverseString = function (a, b, c) {
    const m = [['a', a], ['b', b], ['c', c]].sort((a, b) => b[1] - a[1]);

    const len = Math.ceil(m[0][1] / 2);
    const arr = new Array(len).fill(m[0][0] + m[0][0]);
    if (m[0][1] % 2) arr[len - 1] = m[0][0];

    for (let i = 0; m[1][1] || m[2][1]; i++) {
        if (m[1][1]) arr[i % len] += m[1][0], m[1][1]--;
        else arr[i % len] += m[2][0], m[2][1]--;
    }

    return arr.join('').replace(new RegExp(m[0][0] + '{3,}$'), m[0][0] + m[0][0]);
};

4、执行结果​

image.png