题目描述

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

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

s 是一个尽可能长的快乐字符串。
s 中 最多 有a 个字母 ‘a’、b 个字母 ‘b’、c 个字母 ‘c’ 。
s 中只含有 ‘a’、’b’ 、’c’ 三种字母。
如果不存在这样的字符串 s ，请返回一个空字符串 “”。

样例

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

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

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

算法1

(Greedy) $O(n)$

举例说明， 5个a， 4个b，3个c
1.将字符按剩余个数排序，5个a， 4个b，3个c；
2.选用剩余个数最多的字符，选用2个(如果只剩一个了，那就选1个)，现在字符串是”aa”, 剩余3个a， 4个b，3个c；
3.判断2中使用的字符是否还是最多的，如果仍然是最多的，在字符串末尾加上1个第二多的字符，如果不是最多的，则加上2个现在最多的字符，于是字符串是”aabb”, 剩余3个a， 2个b，3个c；
4.重复以上1~3的操作，
字符串为”aabbaa”, 1个a， 2个b，3个c
-> 字符串为”aabbaacc”, 1个a， 2个b，1个c
-> 字符串为”aabbaaccbb”, 1个a， 0个b，1个c
-> 字符串为”aabbaaccbba”, 0个a， 0个b，1个c
-> 字符串为”aabbaaccbbac”, 0个a， 0个b，0个c
5.结束

时间复杂度

只是一个个字符加上去组成最后的答案，故时间复杂度是$O(n)$

参考文献

真的是神仙做法-。-，字符串真让人头秃。
https://leetcode.com/problems/longest-happy-string/discuss/564277/C%2B%2BJava-a-greater-b-greater-c

C++ 代码

class Solution {
public:
    string longestDiverseString(int a, int b, int c, char c_a='a', char c_b='b', char c_c='c') {
        if (b > a) return longestDiverseString(b, a, c, c_b, c_a, c_c);
        if (c > b) return longestDiverseString(a, c, b, c_a, c_c, c_b);
        // 注意这里的base case，当只剩一种字符的时候，最多只能再加2个，往后就没法满足题目要求了
        if (b == 0) return string(min(a, 2), c_a);  

        int use_a = min(a, 2), use_b = min(b, a - use_a > b ? 1 : 2);
        return string(use_a, c_a) + string(use_b, c_b) + 
               longestDiverseString(a - use_a, b - use_b, c, c_a, c_b, c_c);
    }
};