স্ট্রিং s এবং পূর্ণসংখ্যা k দেওয়া। k টি আডজেসেন্ট সমান ক্যারেক্টার থাকলে সেগুলো মুছে দিন। আর কি মুছানো যাবে না পর্যন্ত চালিয়ে যান। চূড়ান্ত স্ট্রিং রিটার্ন করুন।
উদাহরণ: s="deeedbbcccbdaa", k=3 → "aa" (eee, ccc, bbb, ddd মুছে যায়)।
সমাধানের ধাপসমূহ
- স্ট্যাক ব্যবহার করুন যেটি
pair<char, int>রাখে (ক্যারেক্টার, কাউন্ট)। - প্রতিটি ক্যারেক্টার প্রসেস করুন: টপের ক্যারেক্টার মিললে কাউন্ট বাড়ান, না মিললে নতুন পুশ করুন।
- কাউন্ট == k হলে পপ করুন।
- শেষে স্ট্যাক থেকে স্ট্রিং রিকনস্ট্রাক্ট করুন (রিভার্স করতে হবে)।
C++ উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string removeDuplicates(string s, int k) {
string ans;
vector<pair<char, int>> st;
for (char c : s) {
if (!st.empty() && st.back().first == c) {
st.back().second++;
if (st.back().second == k) st.pop_back();
} else {
st.push_back({c, 1});
}
}
for (auto& p : st) ans.append(p.second, p.first);
return ans;
}
};
int main() {
Solution ob;
cout << ob.removeDuplicates("deeedbbcccbdaa", 3);
}
ইনপুট
"deeedbbcccbdaa" 3
আউটপুট
aa
