“Offer 驾到，掘友接招！我正在参与2022春招打卡活动点击查看活动概况。

1405. 最长快乐字符串

假如字符串中不含有任何 ‘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
解题思路:贪心思想
  • 对字符a,b,c的个数从大到小排序;
  • 每次选择个数最多的字符,假如个数最多的字符不满意条件,则选择次数次多的;
  • 留意代码中cur == res.size()的情况,标明当时现已没有可选择的字符了,完毕while循环,回来答案。(比如输入7,0,0, res应该是”aa”)

using PIC = pair<int,char>;
class Solution {
public:
    string longestDiverseString(int a, int b, int c) {
        string res;
        vector<PIC> v{
            {a,'a'},
            {b,'b'},
            {c,'c'}
        };
        int total = a + b + c;
        while(total > 0){
            sort(v.begin(),v.end(),greater<PIC>()); //降序排序
            int cur = res.size();
            for(auto &[cnt,ch] : v){
                if(cnt==0 || res.size() >= 2 && ch == res.back() && ch == res[res.size()-2])
                    continue;
                res += ch;
                cnt--;
                total--;
                break;
            }
            if(cur == res.size()) break; 
            //假如不进行特判,会导致死循环
            //假如在循环中res的长度没有改动,阐明当时现已没有能够选择的字符了,应当跳出while循环
            //比如aaaaaaaaaaa的这种情况
        }
        return res;
    }
};