मान लीजिए एक स्ट्रिंग s दी गई है, एक k डुप्लिकेट हटाने में स्ट्रिंग s से k आसन्न और समान अक्षरों को चुनकर उन्हें हटाना शामिल है जिससे हटाए गए उपस्ट्रिंग के बाएं और दाएं पक्ष एक साथ जुड़ जाते हैं। हम दिए गए स्ट्रिंग s पर बार-बार k डुप्लिकेट हटाने करेंगे जब तक हम शेष को बदल नहीं सकते। हमें सभी ऐसे डुप्लिकेट हटाने के बाद अंतिम स्ट्रिंग ढूंढनी है। उदाहरण के लिए, यदि s = "deeedbbcccbdaa" और k = 3 है, तो आउटपुट "aa" होगा। पहले "eee" और "ccc" हटाएं, हमें "ddbbbaa" मिलेगा, फिर "bbb" हटाएं, स्ट्रिंग "dddaa" होगी, फिर "ddd" हटाएं, और आउटपुट "aa" होगा।
हल करने के चरण
- ans := खाली स्ट्रिंग
- चार-इंट पेयर के लिए एक स्टैक बनाएं, n := स्ट्रिंग का आकार
- i को 0 से n तक लूप करें
- x := s[i]
- यदि स्टैक खाली नहीं है और स्टैक के शीर्ष तत्व का इंटीजर = k, तो स्टैक से शीर्ष तत्व हटाएं
- यदि i = n, तो ब्रेक करें
- यदि स्टैक खाली है या स्टैक के शीर्ष का कैरेक्टर x नहीं है, तो पेयर (x, 1) को स्टैक में डालें, और i को 1 से बढ़ाएं
- अन्यथा स्टैक के शीर्ष तत्व के इंटीजर भाग को बढ़ाएं, और i को 1 से बढ़ाएं
- जब तक स्टैक खाली नहीं है
- temp := स्टैक का शीर्ष तत्व
- जब तक temp का इंटीजर भाग 0 नहीं है
- ans := ans + temp का कैरेक्टर भाग
- temp के इंटीजर भाग को 1 से घटाएं
- स्टैक से शीर्ष तत्व हटाएं
- ans स्ट्रिंग को रिवर्स करें और वापस करें
उदाहरण
#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
