1405.最长快乐字符串.md

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

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

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

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

eg:

示例 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"
解释：这是该测试用例的唯一正确答案。

思路描述：贪心算法，优先放置数目多的元素，如果上一次插入之后下一次依然是数目最多的，那么插入次多的。比如

a = 7, b = 1, c = 0

先插入两个 a，然后插入一个 b，然后插入两个 a

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        vector<pair<int, char>> vec;
        vec.push_back(make_pair(a, 'a'));
        vec.push_back(make_pair(b, 'b'));
        vec.push_back(make_pair(c, 'c'));
        string ans = ""; 
        char lastChar;
        while(1){
            sort(vec.begin(), vec.end(), [](pair<int, char>&a, pair<int, char>&b){return a.first > b.first;});
            if(vec[0].first == 0) break;
            if(vec[0].second != lastChar){
                int len = vec[0].first >= 2 ? 2 : vec[0].first;
                string s(len, vec[0].second);
                ans += s;
                vec[0].first -= len;
                lastChar = vec[0].second;
            } else if(vec[1].first != 0){
                ans += vec[1].second;
                vec[1].first --;
                lastChar = vec[1].second;
            } else break;
        }
        return ans;
    }
};