C ++中最长的幸福字符串

假设有一个字符串。如果该字符串不包含“ aaa”，“ bbb”或“ ccc”之类的任何字符串作为子字符串，则称为“快乐”。如果我们有三个整数，例如a，b和c，则返回满足以下条件的任何字符串s-

• s是幸福的，也是最长的。

• s最多包含一个字母“ a”的出现，最多包含b个字母“ b”的出现，最多c个字母“ c”的出现。

• s仅包含“ a”，“ b”和“ c”字母。

如果没有这样的字符串，则返回一个空字符串。

因此，如果输入像a = 1，b = 1，c = 7，则输出将为“ ccaccbcc”

为了解决这个问题，我们将遵循以下步骤-

• 定义一个数据结构，其中存在字符a，inx和cnt

• 定义一个优先级队列pq，它将使用cnt数据值确定优先级

• 如果a不为零，则-

• 在pq中插入新的Data（'a'，a，0）

• 如果b不为零，则-

• 在pq中插入新的Data（'b'，b，0）

• 如果c不为零，则-

• 在pq中插入新的Data（'c'，c，0）

• idx：= 1

• ret：=空字符串

• 虽然true为非零，但是-

• 将温度插入pq

• 从循环中出来

• val：= temp和2的最小值

• 值：= 1

• 如果pq为空，则-

• x：=温度

• temp：= pq的顶部元素

• 从pq中删除元素

• 将x插入pq

• 从循环中出来

• temp：= pq的顶部元素

• 从pq中删除元素

• 如果ret的大小不为0并且ret的最后一个元素与temp.a相同，则-

• 值：= 0

• 如果不是pq为空且temp的cnt-pq的第一个元素的cnt <2，则-

• 除此以外

• ret：= ret从val中temp.a的索引连接val到结束

• temp.cnt：= temp.cnt-val

• 如果pq为空，则-

• temp.idx：= idx

• 如果temp.cnt> 0，则-

• （将idx增加1）

• 返回ret

例 

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
struct Data{
   char a;
   int cnt;
   int idx ;
   Data(char c, int x, int k){
      a = c;
      cnt = x;
      idx = k;
   }
};
struct Cmp{
   bool operator()(Data& a, Data& b) {
      return !(a.cnt>b.cnt);
   }
};
class Solution {
public:
   string longestDiverseString(int a, int b, int c) {
      priority_queue<Data, vector<Data>, Cmp> pq;
      if (a)
         pq.push(Data('a', a, 0));
      if (b)
         pq.push(Data('b', b, 0));
      if (c)
         pq.push(Data('c', c, 0));
      int idx = 1;
         string ret = "";
      while (true) {
         Data temp = pq.top();
         pq.pop();
         if (ret.size() && ret.back() == temp.a) {
            if (pq.empty())
               break;
            Data x = temp;
            temp = pq.top();
            pq.pop();
            pq.push(x);
         }
         int val = 0;
         if (!pq.empty() && temp.cnt - pq.top().cnt < 2) {
            val = 1;
         }
         else
            val = min(temp.cnt, 2);
         ret += string(val, temp.a);
         temp.cnt -= val;
         if (pq.empty())
            break;
         temp.idx = idx;
         if (temp.cnt > 0)
            pq.push(temp);
         idx++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   cout << (ob.longestDiverseString(1,1,7));
}

输入值

1,1,7

输出结果

ccbccacc