✅[C++] Using Stack | Monotonic for characters
Concept Used : Monotonic Stack\nSince, we are asked to find a subsequence having all the characters and that too in lexicographical order, therefore stack and p
#### Concept Used : Monotonic Stack\nSince, we are asked to find a subsequence having all the characters and that too in lexicographical order, therefore stack and priority queue should come to your mind. Now, we cannot maintain the relative order with priority queue since it places the smallest at top, but if we need to find an increasing or decreasing subsequence, we choose ***monotonic stack***. \nIn case, you dont know about it, please solve some questions and have a good knowledge of this concept because its widely used in many stack problems. \nHere, we find a subsequence having exactly one occurance of each character and that should be in increasing/lexicographical order. Therefore, we use monotonically increasing stack. Along with it, we maintain a visited array that keeps the check of which elements are present in stack. \nSo, we loop over the string, at each iteration, we decrease the hash of that character, and if stack is empty, we put it in the stack, else, if it is not already present in the stack, then to make it a part of our answer, we put it at its right position, by removing all the characters greater than it. Please note that, if we have an additional condition that `hash[st.top()-\'a\']!=0`, which means we will pop the character from the stack if and only if that occurance of that character is not the last character. If it is the last occurance of that character, we need to keep it in the stack. We cannot pop it. \nFinally, we just put all the characters in an answer string and return it. :) \n\n```\nclass Solution {\npublic:\n    string smallestSubsequence(string s) {\n        stack <char> st;\n        vector <int> hash(26,0);\n        vector <bool> visited(26,false);\n        for(auto u : s) hash[u-\'a\']++;\n        \n        for(int i = 0; i<s.size(); i++){\n            hash[s[i]-\'a\']--;\n            if(st.empty()) st.push(s[i]),visited[s[i]-\'a\']=true;\n            else{\n                if(!visited[s[i]-\'a\']){\n                    while(!st.empty() and s[i]<st.top() and hash[st.top()-\'a\']!=0){ \n                        visited[st.top()-\'a\']=false;\n                        st.pop();\n                    }\n                    st.push(s[i]), visited[s[i]-\'a\']=true;\n                }\n            }\n        }\n        string ans = "";\n        while(!st.empty()) ans.push_back(st.top()), st.pop();\n        reverse(ans.begin(),ans.end());\n        return ans;\n    }\n};\n```
['Stack', 'C', 'Monotonic Stack', 'C++']