C++で最長のハッピーストリング

文字列があるとします。その文字列には、サブ文字列として「aaa」、「bbb」、「ccc」などの文字列が含まれていない場合、ハッピーと呼ばれます。 a、b、cのような3つの整数がある場合は、次の条件を満たす任意の文字列sを返します-

• sは幸せで、可能な限り長くなります。

• sには、最大で文字「a」、最大でb個の文字「b」、および最大でc個の文字「c」が含まれます。

• sには、「a」、「b」、および「c」の文字のみが含まれます。

そのような文字列がない場合は、空の文字列を返します。

したがって、入力がa =1、b =1、c =7の場合、出力は「ccaccbcc」になります

これを解決するには、次の手順に従います-

• 文字a、inx、およびcntが存在する1つのデータ構造を定義します

• 1つの優先キューpqを定義します。これにより、データのcnt値を使用して優先順位が付けられます

• aがゼロ以外の場合、-

  • 新しいData（'a'、a、0）をpqに挿入します

• bがゼロ以外の場合、-

  • 新しいData（'b'、b、0）をpqに挿入します

• cがゼロ以外の場合、-

  • 新しいData（'c'、c、0）をpqに挿入します

• idx：=1

• ret：=空白の文字列

• trueがゼロ以外の場合、実行-

  • temp：=pqの最上位要素

  • pqから要素を削除する

  • retのサイズが0でなく、retの最後の要素がtemp.aと同じである場合、-

    • pqが空の場合、-

      • ループから出てきます

    • x：=temp

    • temp：=pqの最上位要素

    • pqから要素を削除する

    • xをpqに挿入

  • val：=0

  • そうでない場合、pqは空であり、tempのcnt-pq <2の最初の要素のcnt、次に-

    • val：=1

  • それ以外の場合

    • val：=tempと2の最小cnt

  • ret：=retはvalのtemp.aのインデックスからendまでvalを連結します

  • temp.cnt：=temp.cnt --val

  • pqが空の場合、-

    • ループから出てきます

  • temp.idx：=idx

  • temp.cnt> 0の場合、-

    • 温度をpqに挿入

  • （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