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"

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Greedy algorithms

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

Solutions:
class Solution:

	def removeDuplicateLetters(self, s):
		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):
		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):
		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):
		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):
		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):
		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):
		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):
		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