C++刷LeetCode（1405. 最长快乐字符串）【贪心思想】

糖逗

题目描述：

1. 如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。
   
2. 
   
3. 给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：
   
4. 
   
5. s 是一个尽可能长的快乐字符串。
   
6. s 中 最多 有a 个字母 'a'、b 个字母 'b'、c 个字母 'c' 。
   
7. s 中只含有 'a'、'b' 、'c' 三种字母。
   
8. 如果不存在这样的字符串 s ，请返回一个空字符串 ""。
   
9. 
   
10.  
    
11. 
    
12. 示例 1：
    
13. 
    
14. 输入：a = 1, b = 1, c = 7
    
15. 输出："ccaccbcc"
    
16. 解释："ccbccacc" 也是一种正确答案。
    
17. 示例 2：
    
18. 
    
19. 输入：a = 2, b = 2, c = 1
    
20. 输出："aabbc"
    
21. 示例 3：
    
22. 
    
23. 输入：a = 7, b = 1, c = 0
    
24. 输出："aabaa"
    
25. 解释：这是该测试用例的唯一正确答案。
    
26.  
    
27. 
    
28. 提示：
    
29. 
    
30. 0 <= a, b, c <= 100
    
31. a + b + c > 0
    
32. 
    
33. 来源：力扣（LeetCode）
    
34. 链接：https://leetcode-cn.com/problems/longest-happy-string
    
35. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     bool valid(string& res, int pos, string temp){
   
4.         string store = res;
   
5.         store.insert(pos, temp);
   
6.         for(int i = 0; i < store.size() - 2; i++){
   
7.             if(store[i] == temp[0] && store[i+1] == temp[0] && store[i+2] == temp[0])return false;
   
8.         }
   
9.         return true;
   
10.     }
    
11.     string longestDiverseString(int a, int b, int c) {
    
12.         string res;
    
13.         vector<pair<int, string> > store;
    
14.         store.push_back(make_pair(a, "a"));
    
15.         store.push_back(make_pair(b, "b"));
    
16.         store.push_back(make_pair(c, "c"));
    
17.         sort(store.begin(), store.end());
    
18.         string temp1 = "abc";
    
19.         int count1 = store[0].first;
    
20.         for(int i = 0; i < count1; i++)res += temp1;
    
21.         string temp2 = store[1].second + store[2].second;
    
22.         int count2 = store[1].first - store[0].first;
    
23.         for(int i = 0; i < count2; i++)res += temp2;
    
24.         string temp3 = store[2].second;
    
25.         int count3 = store[2].first - store[1].first;
    
26.         for(int i = 0; i < count3; i++){
    
27.             bool flag = false;
    
28.             for(int j = 0; j <= res.size(); j++){
    
29.                 if(valid(res, j, temp3)){
    
30.                     res.insert(j, temp3);
    
31.                     flag = true;
    
32.                     break;
    
33.                 }
    
34.             }
    
35.             if(flag == false)break;
    
36.         }
    
37.         return res;
    
38.     }
    
39. };

复制代码

参考链接：https://leetcode-cn.com/problems ... a-ru-by-time-limit/