[LeetCode] 316. Remove Duplicate Letters

 Problem : https://leetcode.com/problems/remove-duplicate-letters/

To form the smallest string in lexicographical order, we need to put the remaining smallest letters in front.

Time Complexity = O ( N )

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        seen = {}
        used = defaultdict(bool)
        
        # remember the last position the letter be seen
        for i, w in enumerate(s):
            seen[w] = i
        
        result = []
        
        for i, w in enumerate(s):
            if used[w]:
                continue
            
            # replace the selected letter
            # if the letter is larger than current one
            # and we still have this letter in the back
            while result and ord(result[-1]) > ord(w) and seen[result[-1]] > i:
                used[result[-1]] = False
                result.pop()
                
            result.append(w)
            used[w] = True
        
        return ''.join(result)