Python Stack Solution Time: O(N) Space: O(1)
Thoughts on the problem: \n1). I feel like I\'ve seen this problem before. It\'s literally the same problem as 316. https://leetcode.com/problems/remove-duplica
Thoughts on the problem: \n1). I feel like I\'ve seen this problem before. It\'s literally the same problem as 316. https://leetcode.com/problems/remove-duplicate-letters/ Funny enough, that problem is labeled hard while this is labeled medium. Maybe there is difficulty deflation as more problems come out? You can literally paste the same exact code in both problems. \n2). The question is about parsing a string and removing letters. Usually a good idea for parsing letters (or parenthesis!) is a stack so we can have O(1) to remove a letter instead of O(N) each time. \n3). It\'s a string problem with only 26 letters of the alphabet. Great! This means we can probably do O(N) space because O(26N) is O(N). \n\nIntuition to algorithm: We count up the numbers of times each letter appears. We also keep another dictionary that remembers if a character is in our stack or not. At the beginning of each iteration, we decrement the number of times the character can still be encountered in the string in `letterDict`. \nFor each character in our string:\n1). If we have already have the letter in our stack, we skip to the next letter. \n2). If we do not have the letter in our stack and our stack is not empty, we check to see if \n\t\ta. Our current character is smaller than the last character on the stack and \n\t\tb. If the last letter in the stack still exists later on in the string \n\t\tIf a + b is true, we can pop off that last character on the stack. We keep doing a + b until it isn\'t true, then we append our current character \n3). We set that the current character is in the stack by setting it in `used`. \n\nRuntime: O(N) We need to parse the string\nSpace: O(1) We will have at most 26 letters in our stack no matter how long the string is. \n\n```\nclass Solution(object):\n    def smallestSubsequence(self, s):\n        """\n        :type text: str\n        :rtype: str\n        """\n        letterDict = collections.Counter(s)\n        used = {letter: False for letter in "abcdefghijklmnopqrstuvwxyz"}\n        stack = []\n        for char in s:\n            letterDict[char] -= 1\n            if used[char]: continue\n            while stack and ord(char) < ord(stack[-1]) and letterDict[stack[-1]] > 0:\n                used[stack[-1]] = False\n                stack.pop()\n            stack.append(char)\n            used[char] = True\n        return "".join(stack)\n```
[]