मान लीजिए कि एक स्ट्रिंग s दी गई है, k डुप्लिकेट हटाने में स्ट्रिंग s से आसन्न और समान अक्षरों को चुनना और उन्हें हटाना शामिल है, जिससे हटाए गए सबस्ट्रिंग के बाएँ और दाएँ पक्ष एक साथ जुड़ते हैं। हम दिए गए स्ट्रिंग s पर बार-बार k डुप्लिकेट निष्कासन करेंगे, जब तक कि हम किसी भी शेष को नहीं बदल सकते। इस तरह के सभी डुप्लिकेट निष्कासन किए जाने के बाद हमें अंतिम स्ट्रिंग ढूंढनी होगी। इसलिए यदि इनपुट s ="deeedbbcccbdaa", और k =3 जैसा है, तो आउटपुट "आ" होगा, पहले "eee" और "ccc" को हटा दें और हमें "ddbbbaa" मिलेगा, फिर "bbb" को हटा दें। , स्ट्रिंग "dddaa" होगी, फिर "ddd" हटाएं, और आउटपुट "aa" होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- उत्तर:=खाली स्ट्रिंग
- चार-इंट जोड़ी के लिए एक स्टैक बनाएं, n:=स्ट्रिंग का आकार
- मैं के लिए 0 से n की सीमा में
- x :=s[i]
- यदि स्टैक खाली नहीं है और स्टैक के शीर्ष तत्व का पूर्णांक =k, तो स्टैक से शीर्ष तत्व को हटा दें
- अगर i =n, तो ब्रेक करें
- यदि स्टैक खाली है या स्टैक टॉप का वर्ण x नहीं है, तो स्टैक में युग्म (x, 1) डालें, और i को 1 से बढ़ाएँ
- अन्यथा स्टैक टॉप एलीमेंट के पूर्णांक भाग को बढ़ाएँ, और i को 1 से बढ़ाएँ
- जबकि स्टैक खाली नहीं है
- अस्थायी:=स्टैक शीर्ष तत्व
- जबकि अस्थायी का पूर्णांक भाग 0 नहीं है,
- उत्तर:=उत्तर + अस्थायी का वर्ण भाग
- अस्थायी के पूर्णांक भाग को 1 से घटाएं
- स्टैक से शीर्ष तत्व हटाएं
- उत्तर स्ट्रिंग को उल्टा करें और वापस लौटें।
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string removeDuplicates(string s, int k) {
string ans = "";
stack < pair<char, int> > st;
int n = s.size();
for(int i = 0; i <= n;){
char x = s[i];
if(!st.empty() && st.top().second == k)st.pop();
if(i == n)break;
if(st.empty() || st.top().first != x){
st.push({x, 1});
i++;
} else {
st.top().second++;
i++;
}
}
while(!st.empty()){
pair <char, int> temp = st.top();
while(temp.second--) ans += temp.first;
st.pop();
}
reverse(ans.begin(), ans.end());
return ans;
}
};
main(){
Solution ob;
cout <<(ob.removeDuplicates("deeedbbcccbdaa", 3));
} इनपुट
"deeedbbcccbdaa" 3
आउटपुट
aa
