Given a string s, return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

&nbsp;
Example 1:

Input: s = "bcabc"
Output: "abc"


Example 2:

Input: s = "cbacdcbc"
Output: "acdb"


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 1000
	s consists of lowercase English letters.


&nbsp;
Note: This question is the same as 316: https://leetcode.com/problems/remove-duplicate-letters/
class Solution:
    def smallestSubsequence(self, s: str) -> str:
         # calculate the last occurence of each characters in s
        last_occurence = {c: i for i, c in enumerate(s)}
        
        stack = []
        # check if element is in stack
        instack = set()
        for i, c in enumerate(s):
            if c not in instack:
                # check if stack already have char larger then current char
                # and if char in stack will occur later again, remove that from stack
                while stack and stack[-1] > c and last_occurence[stack[-1]] > i:
                    instack.remove(stack[-1])
                    stack.pop()
                    
                instack.add(c)   
                stack.append(c)
        
        return "".join(stack)
class Solution {
    public String smallestSubsequence(String s) {
        boolean[] inStack = new boolean [26];
        int[] lastIdx = new int [26];
        Arrays.fill(lastIdx,-1);
        for(int i = 0; i < s.length(); i++){
            lastIdx[s.charAt(i)-'a'] = i;
        }
        Deque<Character> dq = new ArrayDeque<>();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(inStack[ch-'a']){
                continue;
            }
            while(!dq.isEmpty() && dq.peekLast() > ch && lastIdx[dq.peekLast()-'a'] > i){
                inStack[dq.pollLast()-'a'] = false;
            }
            dq.addLast(ch);
            inStack[ch-'a'] = true;
        }
        StringBuilder sb = new StringBuilder();
        while(!dq.isEmpty()){
            sb.append(dq.pollFirst());
        }
        return sb.toString();
    }
}
class Solution {
public:
    string smallestSubsequence(string s) {
        
        string st="";
        unordered_map< char ,int> m;
        vector< bool> vis( 26,false);
        for( int i=0;i<s.size();i++) m[s[i]]++;
        
        stack< char> t;
        
        t.push(s[0]) , m[s[0]]--;
        st+=s[0];
        vis[s[0]-'a']=true;
        
        for( int i=1;i<s.size();i++){
            
            m[ s[i]]--;
            if(!vis[ s[i]-'a']){
                while( !t.empty() &&  m[t.top()] >0 && t.top() > s[i]){
                    st.pop_back();
                    vis[ t.top()-'a']=false;
                    t.pop();
                }
                t.push(s[i]);
                vis[s[i]-'a']=true;
                st=st+s[i];
            }
        }
        return st;
    }
};
var smallestSubsequence = function(s) {
    let stack = [];
  for(let i = 0; i < s.length; i++){
      if(stack.includes(s[i])) continue;
   while(stack[stack.length-1]>s[i] && s.substring(i).includes(stack[stack.length-1])) stack.pop();
      stack.push(s[i]);
  }
  return stack.join("");
};
Smallest Subsequence of Distinct Characters