मान लीजिए कि हमारे पास एक स्ट्रिंग है जिसमें केवल लोअरकेस अक्षर हैं। हमें सभी डुप्लीकेट अक्षरों को ऐसे हटाना है कि सभी अक्षर केवल एक बार आएं। और हमें परिणाम को सबसे छोटे लेक्सिकोग्राफिक अनुक्रम में प्रदर्शित करना होगा। तो अगर इनपुट “abccb” जैसा है, तो परिणाम “abc” होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
उत्तर:=एक खाली स्ट्रिंग
-
एक स्टैक सेंट परिभाषित करें
-
26 आकार के स्टैक पर एक सरणी परिभाषित करें
-
एक नक्शा परिभाषित करें मी
-
n :=s का आकार
-
प्रारंभ करने के लिए i :=0, जब i
-
m[s[i]] को 1 से बढ़ाएं
-
-
प्रारंभ करने के लिए i :=0, जब i
-
एक सरणी x =s आकार i
. परिभाषित करें -
m[x] को 1 से कम करें
-
अगर onStack[x - 'a'] गैर-शून्य है, तो,
-
अगले पुनरावृत्ति पर जाएं, निम्नलिखित भाग पर ध्यान न दें
-
-
जबकि सेंट खाली नहीं है और x
-
ऑनस्टैक [सेंट के शीर्ष - 'ए']:=झूठा
-
सेंट से आइटम हटाएं
-
-
सेंट में x डालें
-
onStack[x - 'a'] :=true
-
-
जबकि (सेंट खाली है) गलत है, करें -
-
x:=सेंट का शीर्ष तत्व
-
सेंट से आइटम हटाएं
-
उत्तर =उत्तर + 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”