Some Python solutions

• Solutions inspired by those of others. Simpler but less efficient (all still get accepted, of course, in about 50 to 100 ms, normal for Python).

Solution 1

Inspired by lixx2100's explanation.

``````def removeDuplicateLetters(self, s):
for c in sorted(set(s)):
suffix = s[s.index(c):]
if set(suffix) == set(s):
return c + self.removeDuplicateLetters(suffix.replace(c, ''))
return ''
``````

Solution 2

Inspired by WHJ425's explanation.

``````def removeDuplicateLetters(self, s):
result = ''
while s:
i = min(map(s.rindex, set(s)))
c = min(s[:i+1])
result += c
s = s[s.index(c):].replace(c, '')
return result
``````

Solution 3

Inspired by halibut735's 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``````

• great summary!

• can we say the third one is a greedy method?

• What a elegant code! Thanks for your sharing!

• @StefanPochmann Quick question. May you explain how we know to tackle this as a greedy problem rather than a dp problem? Are there general signs that hint to either approach in your experience? Thanks

• Any problem can be solved using dp. Solving using a greedy strategy is harder though, since you need to prove that greedy will work for that problem. There are some tell-tale signs of a problem where greedy may be applicable, but isn't immediately apparent. Example:

1. Choice of an element depends only on its immediate neighbours (wiggle sort).
2. Answer is monotonically non-decreasing or non-increasing (sorting). This is also applicable for LIS for example.
3. Anything that requires lexicographically largest or smallest of something.
4. Anything where processing the input in sorted order will help.
5. Anything where processing the input in forward or reverse (as given) will help.
6. Anything which requires you to track the minimum or maximum of something (think of sliding window problems).

There's matroid theory which deal with greedy algorithms, but I don't really understand it. If someone does, I'll be super grateful to them to explain it to me in simple language!

In general, try to see if for a problem, the solution doesn't depend on a lot of history about the solution itself, but the next part of the solution is somewhat independent from the rest of the solution. These are all indicative of the fact that a greedy strategy could be applicable.

• These are great, as usual. Solution 1 can be tweaked to compare set sizes instead of elementwise equality which speeds it up.

``````    def removeDuplicateLetters(self, s):
s_set = sorted(set(s))
for c in s_set:
suffix = s[s.index(c):]
if len(set(suffix)) == len(s_set):
return c + self.removeDuplicateLetters(suffix.replace(c, ''))
return ""
``````

• @StefanPochmann just curious, what is the time complexity of solution 2?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.