ধরুন একটি স্ট্রিং s দেওয়া হয়েছে, একটি k ডুপ্লিকেট অপসারণে স্ট্রিং s থেকে k সংলগ্ন এবং সমান অক্ষর বেছে নেওয়া এবং সেগুলিকে অপসারণ করা যার ফলে মুছে ফেলা সাবস্ট্রিংটির বাম এবং ডান দিক একসাথে সংযুক্ত হয়। আমরা প্রদত্ত স্ট্রিং s-এ বারবার k ডুপ্লিকেট অপসারণ করব যতক্ষণ না আমরা অবশিষ্ট কোনো পরিবর্তন করতে না পারি। এই জাতীয় সমস্ত সদৃশ অপসারণ করার পরে আমাদের চূড়ান্ত স্ট্রিংটি খুঁজে বের করতে হবে। সুতরাং ইনপুট যদি s =“deeedbbcccbdaa”, এবং k =3 এর মত হয়, তাহলে আউটপুট হবে “aa”, প্রথমে “eee” এবং “ccc” মুছে ফেলুন এবং আমরা “ddbbbaa” পাব, তারপর “bbb” মুছুন। , স্ট্রিংটি হবে "dddaa", তারপর "ddd" মুছে ফেলুন, এবং আউটপুট হবে "aa"
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- উত্তর :=খালি স্ট্রিং
- char-int জোড়ার জন্য একটি স্ট্যাক তৈরি করুন, n :=স্ট্রিংয়ের আকার
- আমি 0 থেকে n
- পরিসরে
- x :=s[i]
- যদি স্ট্যাক খালি না হয় এবং স্ট্যাকের শীর্ষ উপাদানের পূর্ণসংখ্যা =k, তাহলে স্ট্যাক থেকে শীর্ষ উপাদান মুছে ফেলুন
- যদি i =n, তাহলে বিরতি
- যদি স্ট্যাক খালি হয় বা স্ট্যাকের শীর্ষের অক্ষর x না হয়, তাহলে স্ট্যাকের মধ্যে জোড়া (x, 1) ঢোকান এবং i 1 দ্বারা বাড়ান
- অন্যথায় স্ট্যাকের শীর্ষ উপাদানের পূর্ণসংখ্যার অংশ বাড়ান এবং i 1 দ্বারা বাড়ান
- যখন স্ট্যাক খালি থাকে না
- temp :=স্ট্যাক শীর্ষ উপাদান
- যদিও temp-এর পূর্ণসংখ্যা অংশ 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
