题目描述

如果字符串中不含有任何 '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"
解释：这是该测试用例的唯一正确答案。

限制

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

算法

(贪心) $O((a + b + c)^2)$

1. 我们交替地往原字符串中插入 a，b 或 c，且保证每一次插入时都不会破坏规则。
2. 由于是交替地插入，所以如果出现了某个字符不能插入的情况，则说明无论如何都没有办法插入这么多个该字符。

时间复杂度

• 每次寻找可行位置并插入的时间复杂度为 $O(a + b + c)$。
• 最坏情况下，需要插入 a + b + c 次，故时间复杂度为 $O((a + b + c) ^ 2)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储答案。

C++ 代码

class Solution {
public:
    void insert(string &ans, char c) {
        for (int j = 0; j <= ans.length(); j++) {
            if (!( j > 1 && ans[j - 2] == c && ans[j - 1] == c
                || j > 0 && ans[j - 1] == c && ans[j] == c
                || j < ans.length() - 1 && ans[j] == c && ans[j + 1] == c)) {
                ans.insert(j, 1, c);
                break;
            }
        }
    }

    string longestDiverseString(int a, int b, int c) {
        string ans;

        int x = a + b + c, r = 0;
        for (int i = 1; i <= x; i++) {
            if (r == 0) {
                if (a > 0) {
                    insert(ans, 'a');
                    a--;
                } else {
                    i--;
                }
            }

            if (r == 1) {
                if (b > 0) {
                    insert(ans, 'b');
                    b--;
                } else {
                    i--;
                }
            }

            if (r == 2) {
                if (c > 0) {
                    insert(ans, 'c');
                    c--;
                }
                else {
                    i--;
                }
            }

            r = (r + 1) % 3;
        }

        return ans;
    }
};