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