<p>Given a string <code>s</code>, remove duplicate letters so that every letter appears once and only once. You must make sure your result is <span data-keyword="lexicographically-smaller-string"><strong>the smallest in lexicographical order</strong></span> among all possible results.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;bcabc&quot;
<strong>Output:</strong> &quot;abc&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;cbacdcbc&quot;
<strong>Output:</strong> &quot;acdb&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 10<sup>4</sup></code></li>
	<li><code>s</code> consists of lowercase English letters.</li>
</ul>

<p>&nbsp;</p>
<p><strong>Note:</strong> This question is the same as 1081: <a href="https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/" target="_blank">https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/</a></p>

class Solution {
public:
    string removeDuplicateLetters(string s) {
         int n=s.size();
         unordered_map<char,int>mp;
         for(int i=0;i<n;i++)
         {
            mp[s[i]]++;
         }
         vector<bool>vis(26,false);
         stack<char>st;
         for(int i=0;i<n;i++)
         {
            while(!st.empty()&&!vis[s[i]-'a']&&(s[i]<=st.top())&&mp[st.top()]>0)
            {
                    vis[st.top()-'a']=false;
                    st.pop();
            }
         //   mp[s[i]]--;
           if(vis[s[i]-'a']==false)
           { 
            st.push(s[i]);
            vis[s[i]-'a']=true;
            }
            mp[s[i]]--;
         }
         while(!st.empty()&&mp[st.top()]>1)
         {
                mp[st.top()]--;
                st.pop();
         }
         string str;
         while(!st.empty())
         {
             str+=st.top();
             st.pop();
         }

         reverse(str.begin(),str.end());
         return str;
    }
};
9700