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 में नया डेटा ('a', a, 0) डालें

• अगर b गैर-शून्य है, तो -

  • pq में नया डेटा ('b', b, 0) डालें

• अगर c गैर-शून्य है, तो -

  • pq में नया डेटा ('c', c, 0) डालें

• आईडीएक्स :=1

• रिट:=खाली स्ट्रिंग

• जबकि सत्य गैर-शून्य है, करें -

  • अस्थायी:=pq का शीर्ष तत्व

  • pq से तत्व हटाएं

  • यदि रिट का आकार 0 नहीं है और रिट का अंतिम तत्व temp.a के समान है, तो -

    • अगर pq खाली है, तो -

      • लूप से बाहर आएं

    • एक्स:=अस्थायी

    • अस्थायी:=pq का शीर्ष तत्व

    • pq से तत्व हटाएं

    • pq में x डालें

  • वैल:=0

  • यदि pq खाली नहीं है और pq <2 के पहले तत्व के अस्थायी - cnt का नहीं है, तो -

    • वैल:=1

  • अन्यथा

    • वैल :=न्यूनतम सीएनटी टेम्परेचर और 2

  • रिट:=वैल से अंत तक temp.a के इंडेक्स से रिट कॉन्टेनेट वैल

  • temp.cnt:=temp.cnt - वैल

  • अगर pq खाली है, तो -

    • लूप से बाहर आएं

  • temp.idx:=idx

  • अगर temp.cnt> 0, तो -

    • pq में अस्थायी डालें

  • (आईडीएक्स को 1 से बढ़ाएं)

• वापसी रिट

उदाहरण

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

#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