Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.
 
Example 1:
 
 
Input: "bcabc"
Output: "abc"
 
 
Example 2:
 
 
Input: "cbacdcbc"
Output: "acdb"

Difficulty: interview

Starter code:

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        

Solutions:
class Solution:
     def removeDuplicateLetters(self, s):
         """
         :type s: str
         :rtype: str
         """
         rindex = {c: i for i, c in enumerate(s)}
         result = ''
         for i, c in enumerate(s):
             if c not in result:
                 while c < result[-1:] and i < rindex[result[-1]]:
                     result = result[:-1]
                 result += c
         return result

class Solution:
     def removeDuplicateLetters(self, s):
         """
         :type s: str
         :rtype: str
         """
         chars = set(s)
         for c in sorted(chars):
             suffix = s[s.index(c):]
             if set(suffix) == chars:
                 return c + self.removeDuplicateLetters(suffix.replace(c, ''))
         return ''


class Solution:
     def removeDuplicateLetters(self, s):
         if not s or len(s) <= 1:
             return s
         
         from collections import Counter
         count = Counter(s)
         seen = set([])
         stack = []
         
         i = 0
         while i < len(s):
             char = s[i]
             if char not in seen:
                 if stack and ord(stack[-1]) > ord(char) and count[stack[-1]] >= 1:
                     ele = stack.pop()
                     seen.remove(ele)
                 else:
                     count[char] -= 1
                     seen.add(char)
                     stack.append(char)
                     i += 1
             else:
                 count[char] -= 1
                 i += 1
         
         return ''.join(stack)

class Solution:
     def removeDuplicateLetters(self, s):
         """
         :type s: str
         :rtype: str
         """
         str_index = {char: i for i, char in enumerate(s)}
         result = ''
         for i, char in enumerate(s):
             if char not in result:
                 while char < result[-1:] and i < str_index[result[-1]]:
                     result = result[:-1]
                 result += char
         return result


class Solution:
     def removeDuplicateLetters(self, s):
         """
         :type s: str
         :rtype: str
         """
         if len(s) == 0: return ''
         count = collections.Counter(s)
         stack = []
         visited = set()
         for c in s:
             count[c] -= 1
             if c in visited: continue
             visited.add(c)
             while stack and stack[-1] > c and count[stack[-1]] > 0:
                 visited.remove(stack[-1])
                 stack.pop()
             stack.append(c)
         
         return ''.join(stack)


class Solution:
     def removeDuplicateLetters(self, s):
         ret = ''
         while s:
             p = min(s.rindex(c) for c in set(s))
             c = min(s[:p + 1])
             ret += c
             s = s[s.index(c):].replace(c, '')
         return ret

class Solution:
     def removeDuplicateLetters(self, s):
         """
         :type s: str
         :rtype: str
         """
         counter = collections.Counter(s)
         added = set()
         ans = []
         for c in s:
             while len(ans) > 0 and c < ans[-1] and counter[ans[-1]] > 0 and c not in added:
                 added.remove(ans.pop())
             counter[c] -= 1
             if c not in added:
                 ans.append(c)
             added.add(c)
         return ''.join(ans)

class Solution:
     def removeDuplicateLetters(self, s):
         """
         :type s: str
         :rtype: str
         """
         counts = {}
         for c in s:
             if c not in counts:
                 counts[c] = 0
             counts[c] += 1
 
         stack = []
         visited = set()
         for c in s:
             counts[c] -= 1
             if c in visited:
                 continue
             while stack and stack[-1] > c and counts[stack[-1]] > 0:
                 visited.remove(stack.pop())
 
             stack.append(c)
             visited.add(c)
 
         return ''.join(stack)


class Solution:
     def removeDuplicateLetters(self, s):
         if not s:
             return ""
         
         res = ''
         sorted_set = sorted(set(s))
         
         for c in sorted_set:
             sub_s = s[s.index(c):]
             if set(s) == set(sub_s):
                 return c + self.removeDuplicateLetters(sub_s.replace(c, ''))
         
                 
         return res


class Solution:
     def removeDuplicateLetters(self, s):
         """
         :type s: str
         :rtype: str
         """
         
         if len(s) <= 1:
             return s
         
         
         for c in sorted(list(set(s))):
             suffix = s[s.index(c):]
             if set(s) == set(suffix):
                 return c + self.removeDuplicateLetters(suffix.replace(c, ''))
         
         return ''
                     
         
         
             


class Solution:
     def removeDuplicateLetters(self, s):
         """
         :type s: str
         :rtype: str
         """
         for c in sorted(set(s)):
             suffix = s[s.index(c):]
             if set(suffix) == set(s):
                 return c + self.removeDuplicateLetters(suffix.replace(c, ''))
         return ''

class Solution:
     def removeDuplicateLetters(self, s):
         """
         :type s: str
         :rtype: str
         """
         for c in sorted(list(set(s))):
             substr = s[s.index(c):]
             if set(substr) == set(s):
                 return c + self.removeDuplicateLetters(substr.replace(c,""))
         return s