2022.02.07

1405. 最长快乐字符串

https://leetcode-cn.com/problems/longest-happy-string/

如果字符串中不含有任何 '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

&emsp;学到的知识点：贪心法的应用
&emsp;第一眼看到这题，想到的方法是先构造一个字符串，其内容满是a,b,c中最多的那一个，然后用剩下两种字符插入这个字符串，为了实现这个思路，需要分很多种情况（如最初的字符串能/不能全部用上等等），太麻烦了，写了一大堆还是有各种遗漏的情况。过程中想到一种与官方题解类似的方法，也是每次取剩余最多的字符，但是根据另外两种字符的数量决定拿一个还是拿两个，但是最后没有去实现这个思路。
&emsp;官方的思路是，每次往答案字符串的末尾插入一个剩余最多的字符，如果这个字符不能放，则找第二多的字符，直到至少有两种字符全部用完。
&emsp;C++：（和官方的有点不同，主要是退出while循环的条件那里）

class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        vector<pair<char,int>> vec;
        vec.push_back(make_pair('a',a));
        vec.push_back(make_pair('b',b));
        vec.push_back(make_pair('c',c));
        sort(vec.begin(),vec.end(),[](pair<char,int> p1,pair<char,int> p2){
            return p1.second>=p2.second;
        });
        if(vec[0].second==1 && vec[1].second==0){
            return string(1,vec[0].first);
        }
        string ans="";
        while(1){
            sort(vec.begin(),vec.end(),[](pair<char,int> p1,pair<char,int> p2){
                return p1.second>=p2.second;
            });
            for(int i=0;i<3;i++){
                int siz=ans.size();
                if(vec[i].second<=0){
                    break;
                }
                if(siz>=2 && ans[siz-2]==vec[i].first && ans[siz-1]==vec[i].first){
                    continue;
                }
                ans.push_back(vec[i].first);
                vec[i].second--;
                break;
            }
            int siz=ans.size();
            if(siz>=2 && ans[siz-2]==vec[0].first && ans[siz-1]==vec[0].first && vec[1].second<=0){
                break;
            }
            else if(vec[0].second==0 && vec[1].second==0 && vec[2].second==0){
                break;
            }
        }
        return ans;
    }
};