1081 Smallest Subsequence of Distinct Characters

思路也是很奇妙的一道题，我们首先处理出来每个字符的index list, 在这个list中，我们每次按照字母的顺序，选取存在的第一个，出现的index小于其他后面后面任何的最后出现index.

例子如下：

s = 'cdadabcc',scontainsa, b, c, d
index['a'] = [2, 4]
index['b'] = [5]
index['c'] = [0, 6, 7]
index['d'] = [1, 3

Which will be the first letter in ans?
It will be letter 'a', cause2 < min(5, 7, 3), (5,7,3) is thelast indexof other letters, after append 'a', now the index becomes
index['b'] = [5]
index['c'] = [6, 7]
index['d'] = [3]

We delete all index less than 2. Obviously, the next letter will be 'd', analyse one by one.

class Solution(object):
    def smallestSubsequence(self, text):
        """
        :type text: str
        :rtype: str
        """
        n = len(text)
        d = collections.defaultdict(collections.deque)
        for i, v in enumerate(text):
            d[ord(v) - ord('a')].append(i)

        keys = sorted(d.keys())
        res = []
        c = len(d)
        last_index = -1
        while len(res) < c:
            for i in range(len(keys)):
                if all(d[keys[i]][0] < d[keys[j]][-1] for j in range(i+1, len(keys))):
                    res.append(chr(ord('a') + keys[i]))
                    last_index = d[keys[i]][0]
                    keys.remove(keys[i])
                    break
            for i in range(len(keys)):
                while d[keys[i]] and d[keys[i]][0] < last_index:
                    d[keys[i]].popleft()
        return ''.join(res)