Beats 100% C++ | Monotonic Stack
Approach\nWe have to choose the biggest element at as last as possible,\nfor that we keep a track of when every element is occuring last in the array.\nNow we h
# Approach\nWe have to choose the biggest element at as last as possible,\nfor that we keep a track of when every element is occuring last in the array.\nNow we have to keep the order as monotonic as possible so we decide to use a monotonic stack.\nWhile pushing any element we check that - \n* it should not be already pushed\n* We pop all the bigger elements that that element provided we can find those elements somtime later in the array during our iteration.\n\n# Complexity\n- Time complexity:\nO(N)\n\n- Space complexity:\nO(26)\n\n# Code\n```\nclass Solution {\npublic:\n    string smallestSubsequence(string a) {\n        int n=a.size();\n        unordered_map<char,int>last;\n        unordered_map<char,int>pushed;\n        for(int i=0;i<n;i++) last[a[i]]=i;\n\n        stack<char>s;\n\n        for(int i=0;i<n;i++){\n            if(s.empty()){\n                s.push(a[i]);\n                pushed[a[i]]=true;\n                continue;\n            }\n\n            while(!s.empty() && s.top()>=a[i] && last[s.top()]>=i && pushed[a[i]]==false){\n                pushed[s.top()]=false;\n                s.pop();\n            }\n\n            if(pushed[a[i]]==false){\n                s.push(a[i]);\n                pushed[a[i]]=true;\n            }\n        }\n\n        string ans;\n\n        while(!s.empty()){\n            ans.push_back(s.top());\n            s.pop();\n        }\n\n        reverse(ans.begin(),ans.end());\n\n        return ans;\n    }\n};\n```
['Monotonic Stack', 'C++']