# Python solution with detailed explanation

• Solution

Remove Duplicate Letters https://leetcode.com/problems/remove-duplicate-letters/

Brute Force

• At every index in string, we can either choose the character or ignore the character.
``````class Solution(object):
def helper(self, idx, s, so_far, N):
if len(so_far) == N:
ssofar = "".join(so_far)
if self.min_so_far == None:
self.min_so_far = ssofar
else:
self.min_so_far = min(self.min_so_far, ssofar)
elif idx == len(s):
return
else:
ch = s[idx]
if ch not in so_far:
so_far.append(ch)
self.helper(idx+1, s, so_far, N)
so_far.pop()
self.helper(idx+1,s,so_far,N)
return

def removeDuplicateLetters(self, inp):
"""
:type s: str
:rtype: str
"""
self.min_so_far = None
N = len(set(inp))
self.helper(0, inp, [], N)
return self.min_so_far
``````

Optimized N^2 Solution

• N^2 solution will be to trigger a search for all characters smaller than or equal to ch at the last occuring index for ch. So if ch = "u" is at index, 2,5,7,9; then at index 9, find all characters less than equal to u in increasing order.
• We do the above by sorting all characters with their indices from start to index of "u". In this increasing set, we find the longest run such that each successive index is larger than previous. Make sure to handle the case of duplicates in this set - we want the first occurence to build the longest chain.
• Another important variable is "start". This indicates the position where we will start searching when we next hit a single frequency character. We want to start from the position we left.
• Another approach to search for candidates before last occurence of a character could be to search in sorted order of unique characters. Find all unique characters. Sort them. Then sequentially search for each of them within start to idx+1. Apply appropriate optimizations.
• https://discuss.leetcode.com/topic/31404/a-short-o-n-recursive-greedy-solution/2
``````class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
idx_map = {ch:idx for idx,ch in enumerate(s)}
ss = sorted(idx_map.items(), key=lambda x:x[1])
result, included = [], set([])
start = 0
for ch, idx in ss:
if ch in included:
continue
candidates = []
for i in range(start,idx+1):
c = s[i]
if c not in included and c <= ch :
candidates.append((i,c))
candidates.sort(key=lambda x:x[1])
for i,x in candidates:
if x not in included and (result == [] or result[-1][0] < i):
result.append((i,x))