ধরুন আমাদের একটি স্ট্রিং আছে যা শুধুমাত্র ছোট হাতের অক্ষর নিয়ে গঠিত। আমাদের সমস্ত ডুপ্লিকেট অক্ষরগুলিকে মুছে ফেলতে হবে যাতে সমস্ত অক্ষর শুধুমাত্র একবার আসে। এবং আমাদের ফলাফলটি ক্ষুদ্রতম লেক্সিকোগ্রাফিক ক্রমানুসারে প্রদর্শন করতে হবে। সুতরাং ইনপুট যদি “abccb” এর মত হয়, তাহলে ফলাফল হবে “abc”
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
উত্তর :=একটি খালি স্ট্রিং
-
একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন
-
26 আকারের স্ট্যাকের উপর একটি অ্যারে সংজ্ঞায়িত করুন
-
একটি মানচিত্র m
সংজ্ঞায়িত করুন -
n :=s
এর আকার -
শুরু করার জন্য i :=0, যখন i
-
1
দ্বারা m[s[i]] বাড়ান
-
-
শুরু করার জন্য i :=0, যখন i
-
একটি অ্যারে x =s আকার i
সংজ্ঞায়িত করুন -
1
দ্বারা m[x] হ্রাস করুন -
যদি onStack[x - 'a'] অ-শূন্য হয়, তাহলে,
-
পরবর্তী পুনরাবৃত্তিতে যান, নিম্নলিখিত অংশটি উপেক্ষা করুন
-
-
যখন st খালি নয় এবং x
-
onStack[st-'a'] :=মিথ্যা
-
st
থেকে আইটেম মুছুন
-
-
st
-এ x ঢোকান -
onStack[x - 'a'] :=সত্য
-
-
যখন (st খালি) মিথ্যা, −
করুন-
x :=st
এর শীর্ষ উপাদান -
st
থেকে আইটেম মুছুন -
ans =ans + x
-
-
অ্যারে রিভার্স রিভার্স করুন
-
উত্তর ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
string removeDuplicateLetters(string s) {
string ans = "";
stack <char> st;
vector <int> onStack(26);
map <char, int> m;
int n = s.size();
for(int i = 0; i < n; i++){
m[s[i]]++;
}
for(int i = 0; i < n; i++){
char x = s[i];
m[x]--;
if(onStack[x - 'a'])continue;
while(!st.empty() && x < st.top() && m[st.top()]){
onStack[st.top() - 'a'] = false;
st.pop();
}
st.push(x);
onStack[x - 'a'] = true;
}
while(!st.empty()){
char x = st.top();
st.pop();
ans += x;
}
reverse(ans.begin(), ans.end());
return ans;
}
};
main(){
Solution ob;
cout << (ob.removeDuplicateLetters("abccb"));
} ইনপুট
“abccb”
আউটপুট
“abc”
