मान लीजिए एक स्ट्रिंग है। उस स्ट्रिंग को हैप्पी कहा जाता है यदि उसमें 'aaa', 'bbb' या 'ccc' जैसे कोई सबस्ट्रिंग नहीं हैं। यदि हमारे पास a, b और c जैसे तीन इंटीजर हैं, तो कोई भी स्ट्रिंग s लौटाएं, जो निम्न शर्तों को पूरा करती हो:
s हैप्पी और यथासंभव लंबी है।
s में अधिकतम a बार 'a', अधिकतम b बार 'b' और अधिकतम c बार 'c' अक्षर हैं।
s में केवल 'a', 'b' और 'c' अक्षर होंगे।
यदि ऐसी कोई स्ट्रिंग नहीं है, तो खाली स्ट्रिंग लौटाएं।
इसलिए, यदि इनपुट है a = 1, b = 1, c = 7, तो आउटपुट "ccaccbcc" होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
एक डेटा स्ट्रक्चर परिभाषित करें जहां कैरेक्टर a, inx और cnt मौजूद हो
एक प्रायोरिटी क्यू pq परिभाषित करें, जो डेटा के cnt मान का उपयोग करके प्राथमिकता देगा
यदि a नॉन-जीरो है, तो -
new Data('a', a, 0) को pq में डालें
यदि b नॉन-जीरो है, तो -
new Data('b', b, 0) को pq में डालें
यदि c नॉन-जीरो है, तो -
new 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 के पहले एलिमेंट का cnt < 2, तो -
val := 1
अन्यथा
val := min(temp का cnt, 2)
ret := ret + temp.a में val इंडेक्स से अंत तक जोड़ें
temp.cnt := temp.cnt - val
यदि pq खाली है, तो -
लूप से बाहर आएं
temp.idx := idx
यदि temp.cnt > 0, तो -
temp को 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
