Chuỗi hạnh phúc dài nhất trong C ++

Giả sử có một chuỗi. Chuỗi đó được gọi là happy nếu nó không có bất kỳ chuỗi nào như 'aaa', 'bbb' hoặc 'ccc' làm chuỗi con. Nếu chúng ta có ba số nguyên như a, b và c, thì trả về bất kỳ chuỗi s nào thỏa mãn các điều kiện sau -

• s hạnh phúc và lâu nhất có thể.

• s chứa nhiều nhất một lần xuất hiện của chữ 'a', nhiều nhất b lần xuất hiện của chữ 'b' và nhiều nhất c lần xuất hiện của chữ 'c'.

• s sẽ chỉ chứa các chữ cái 'a', 'b' và 'c'.

Nếu không có chuỗi như vậy, thì trả về một chuỗi trống.

Vì vậy, nếu đầu vào là a =1, b =1, c =7, thì đầu ra sẽ là "ccaccbcc"

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một cấu trúc dữ liệu có ký tự a, inx và cnt

• Xác định một hàng đợi ưu tiên pq, điều này sẽ ưu tiên sử dụng giá trị cnt của dữ liệu

• nếu a khác 0 thì -

  • chèn Dữ liệu mới ('a', a, 0) vào pq

• nếu b khác 0 thì -

  • chèn Dữ liệu mới ('b', b, 0) vào pq

• nếu c khác 0 thì -

  • chèn Dữ liệu mới ('c', c, 0) vào pq

• idx:=1

• ret:=chuỗi trống

• trong khi true là khác 0, do -

  • temp:=phần tử hàng đầu của pq

  • xóa phần tử khỏi pq

  • nếu kích thước của ret không phải là 0 và phần tử cuối cùng của ret giống với temp.a, thì -

    • nếu pq trống, thì -

      • Ra khỏi vòng lặp

    • x:=temp

    • temp:=phần tử hàng đầu của pq

    • xóa phần tử khỏi pq

    • chèn x vào pq

  • val:=0

  • nếu không pq trống và cnt của temp - cnt của phần tử đầu tiên của pq <2, thì -

    • val:=1

  • Nếu không

    • val:=tối thiểu cnt của nhiệt độ và 2

  • ret:=ret nối val từ chỉ mục của temp.a trong val đến cuối

  • temp.cnt:=temp.cnt - val

  • nếu pq trống, thì -

    • Ra khỏi vòng lặp

  • temp.idx:=idx

  • nếu temp.cnt> 0, thì -

    • chèn tạm thời vào pq

  • (tăng idx lên 1)

• trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

1,1,7

Đầu ra

ccbccacc