<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:
#     def removeDuplicateLetters(self, s: str) -> str:
#         #Remove dup letters so that every letter appears once and only once 
#         #And also return the SMALLEST lexicographical order of the results
#         last_seen = collections.defaultdict(int)
#         for pos, char in enumerate(s):
#             last_seen[char] = pos
#         min_str = []
        
#         seen_at = collections.defaultdict(int)
#         for pos, char in enumerate(s): 
            
#             if char not in seen_at: 
#                 while min_str and char < min_str[-1] and seen_at[min_str[-1]] < last_seen[min_str[-1]]: 
#                     remove_char = min_str.pop()
#                     del seen_at[remove_char]
                
#                 min_str.append(char)
#             seen_at[char] = pos
            
#         return "".join(min_str)
# class Solution:
#     def removeDuplicateLetters(self, s) -> int:
#         #Dup letter appearing once but the uniq letter need to be smallest string
#         #Dec_stack
#         min_stack = []
#         seen_at = collections.defaultdict(int)
#         for pos, char in enumerate(s):
#             seen_at[char] = pos
            
#         first_seen = set()
#         for pos, char in enumerate(s): 
#             if char not in first_seen:
#                 #Clean it up
#                 while min_stack and char < min_stack[-1] :
#                     min_char = min_stack[-1]
                    
#                     last_pos = seen_at[min_char]
#                     if pos < last_pos: 
#                         first_seen.discard(min_char)
#                         min_stack.pop()
#                         # min_stack.append(char)

#                     else: break
#                 min_stack.append(char)
#                 first_seen.add(char)
#         return "".join(min_stack)
#self try 11/21/20
#Best way using the position i.e even tho pos isn't the position of the one we're deleting
#We want to ensure that the pos we're going to add is < the last position of that char since the
#pos will either contain the last or not contain it (i.e use one from before) in which case if it's containg the last one we dont' want to pop it 
class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        """
        Removes duplicate letters from the string s so that every letter appears once and only once.
        The result is the smallest in lexicographical order among all possible results.

        :param s: The input string containing lowercase English letters.
        :return: A string with duplicate letters removed and in smallest lexicographical order.
        """
        from collections import defaultdict
        #monotonically increasing 
        # Step 1: Count the frequency of each character in the string
        count = defaultdict(int)
        for char in s:
            count[char] += 1

        stack = []          # Stack to build the result
        visited = set()     # Set to keep track of characters in the stack

        # Step 2: Iterate through each character in the string
        for char in s:
            # Decrement the count for the current character
            count[char] -= 1

            # If the character is already in the stack, skip it
            if char in visited:
                continue

            # Step 3: Maintain characters in increasing lex order in the stack
            while stack and char < stack[-1] and count[stack[-1]] > 0:
                removed_char = stack.pop()    # Remove the last character
                visited.remove(removed_char)  # Mark it as not visited

            # Step 4: Add the current character to the stack and mark as visited
            stack.append(char)
            visited.add(char)

        # Step 5: Join the stack to form the result string
        return ''.join(stack)

# class Solution:
#     def removeDuplicateLetters(self, s) -> int:
      
#         last_char_pos = collections.defaultdict(int)
        
#         #Make a table of your last seen position for the characters in the string 
#         for pos, char in enumerate(s):
#             last_char_pos[char] = pos 
            
            
#         #You can use that to build your string 
#         #And clean up to make sure it's the unique or at least at it's last unique character 
#         seen_char = set()
#         min_order_str = []
        
        
#         for pos, char in enumerate(s): 
#             if char not in seen_char: 
#                 #while min_order_str exists AND the character is less than our last char result you will
#                 #Remove the results that are > then char since that's not lexigraphical 
#                 #You also need to make sure you are NOT at the "last pos" of your character
#                 #As that is still a valid solution then if it's last pos 
                
#                 #More on the pos < last_char_pos[min_order_str[-1]] 
#                 #We are saying that the previous two and statements is there is a min_order_str
#                 #As well as our CURRENT letter wants to pop out the last letter of min_order_str b/c our current letter is smaller.
#                 #You can use the pos as a reference to know if you're AT the last occurence of the letter that's gonna be popped 
#                 #If it is (you can't pop since it requires every unique character) 
#                 #If it's not i.e examle 1 we know we'll see "b" again later on so is okay. 
#                 while min_order_str and char < min_order_str[-1] and pos < last_char_pos[min_order_str[-1]]:
#                     remove_char = min_order_str.pop()
#                     seen_char.discard(remove_char)

#                 #else the character haven't been seen but it is a valid letter that's not less than or is the last char of it 
#                 # so no need to remove
#                 seen_char.add(char)
#                 min_order_str.append(char)
                
#         return "".join(min_order_str)


# class Solution:
#     def removeDuplicateLetters(self, s) -> int:
#         #get the lexigraphical order 
#         last_seen_pos = collections.defaultdict(int)
        
#         #This will be the character with it's LAST seen position (i.e most recent)
#         for pos, char in enumerate(s):
#             last_seen_pos[char] = pos
        
#         #This will be the character with it's LAST seen position (i.e most recent)
#         # print(last_seen_pos)
        
#         min_order_str = []
#         seen_letter = set()
#         # new_order_str = []
#         #make sure you are at the last position before you append 
#         for pos, char in enumerate(s): 
#             #build the min_order_str with the string so far
#             if char not in seen_letter:
#                 while min_order_str and char < min_order_str[-1] and pos < last_seen_pos[min_order_str[-1]]: 
#                     #either start a new min_order_str or extend the current min_order_str
#                     remove_char = min_order_str.pop()
#                     #This means our seen set needs to be updated accordingly. 
#                     seen_letter.discard(remove_char)
#                 seen_letter.add(char)
#                 min_order_str.append(char)
            
#         return "".join(min_order_str)
# class Solution:
#     def removeDuplicateLetters(self, s) -> int:

#         stack = []

#         # this lets us keep track of what's in our solution in O(1) time
#         seen = set()

#         # this will let us know if there are no more instances of s[i] left in s
#         last_occurrence = {c: i for i, c in enumerate(s)}


#         for i, c in enumerate(s):

#             # we can only try to add c if it's not already in our solution
#             # this is to maintain only one of each character
#             if c not in seen:
#                 # if the last letter in our solution:
#                 #    1. exists
#                 #    2. is greater than c so removing it will make the string smaller
#                 #    3. it's not the last occurrence
#                 # we remove it from the solution to keep the solution optimal
#                 while stack and c < stack[-1] and i < last_occurrence[stack[-1]]:
#                     seen.discard(stack.pop())
#                 seen.add(c)
#                 stack.append(c)
#         return ''.join(stack)
# class Solution(object):
#     def removeDuplicateLetters(self, s):
#         """
#         :type s: str
#         :rtype: str
#         """
#         '''Let's start with having three DS - counter for all the character frequecies in the string
#                                             - a boolean list for the characters which we encounter so that we can skip them once they are encountered
#                                             - a stack to store the lexicographically appropriate order of the string without the duplicates
#         '''
#         countList = [0]*26
#         boolList = [False]*26
#         stack = []
#         '''Initializer the counter array'''
#         for character in s:
#             countList[ord(character) - ord('a')] += 1

#         '''Traverse the given string'''
#         for character in s:
#             '''Decrease the count in the counter array as we came across this letter in a respective iteration'''
#             countList[ord(character)- ord('a')] -= 1
#             '''skip the character altogether if we have encountered it already'''
#             if boolList[ord(character) - ord('a')]:
#                 continue

#             '''if the stack is not empty and the iterator points to a character which is smaller than the last element in the stack --> we need to skip all the characters in the stack which are bigger than the current item. And we can only skip the items if there is a chance of encountering them in the future so we also should check for this in this while loop threshold statment'''
#             while stack and character<stack[-1] and countList[ord(stack[-1]) - ord('a')] >0:
#                 '''the control comes here only if the logic found candidates to be removed from the stack. Hence lets just reverse the boolean values for these items as we should consider them fresh new items when we encounter them in the future so that we don't skip them'''
#                 boolList[ord(stack[-1]) - ord('a')] = False
#                 '''pop the item'''
#                 stack.pop()

#             '''just add the item to the stack'''
#             stack.append(character)

#             '''Don't forget to switch the boolean key ON for this item, so we can skip it, if possible'''
#             boolList[ord(character) - ord('a')] = True 

#         return ''.join(stack)

# class Solution:
#     def removeDuplicateLetters(self, s: str) -> str:
#         #Given a string
#         #Remove duplicate letter so that every letter appears once and only once 
#         #You must make sure the result is the smallest lexigraphical order among all possible results.
        
#         #get's the position of the last seen position 
#         last_seen_pos = collections.defaultdict(int)
        
        
#         for index, char in enumerate(s): 
#             last_seen_pos[char] = index 
            
            
#         # we want to get the smallest order of all possible results 
#         #:a: 2   
#         #b: 3 
#         #c: 4 
        
#             #a I need to add in the bc so I need to check if it's lexigraphical 
            
#         res_letters = [] #abc 
        
        
#         for pos, char in enumerate(s): 
            
#             # print(pos) # -> 0, 1, 2, 3 
#             # print(char) # -> b, c, a, b 
#             if char not in res_letters: #You aren't a repeat result that we will be adding 
#                 #This will either extend you or create a new sequence. 
#                 # if the last letter in our solution:
#                 #    1. exists
#                 #    2. is greater than c so removing it will make the string smaller
#                 #    3. it's not the last occurrence
#                 # we remove it from the solution to keep the solution optimal
                 
#                  # 0 1 u don't want to pop because it could be the last b that's why you need the 
#                 #pos < last_seen_pos[res_letters[-1]] on the same line 
#                 #b a 
                
#                 # res_letters is [b] char is a 
#                 #Make sure it's not the "last" letter because if it is you don't want to pop it from the stack. 
#                 while res_letters and char < res_letters[-1] and pos < last_seen_pos[res_letters[-1]]:
#                     res_letters.pop()
                
#                 res_letters.append(char) 
#                 #res_letters -> b 
                
#         res_str_letters = "".join(res_letters)
#         return res_str_letters
16300