移除重复字母

概述

---

给一串小写字母，需要你从中删除所有重复的字母，保持剩下的字母的相对顺序不变，使得剩下的字符串是所有可能的结果中字典序最小的，求剩下的字符串。

原题

---

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:
Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

分析

---

题目一下子不那么好理解，首先字典序就是一串字符在字典中的顺序，其实也就是Python中字符串比较大小的方法。去重则是把重复的字母去掉，只留下一个，但是留下哪一个，就是不同的结果，导致结果中字母顺序不同。于是我们要找出所有可能的结果中字典序最小的那一个。

思路

---

因为要字典序，所以一定是先确定那个字母排在第一位，第一个字母确定之后再确定第二个字母。
如何确定第一个字母？很容易想到，首先看有没有a，如果有，尽量把a放在最前，也就是把第一个a之前的字母全部删掉。但是如果有的字母只在第一个a之前出现，那么a就不能放在第一个，否则这个字母的所有副本都会被删掉。如果a不能在第一个位置，就接着看b能不能在第一个位置，以此类推。
确定第一个字母之后，把这个字母之前的字母全部删掉，该字母之后重复出现的也删掉，然后从剩下的字母中字典序最小的字母开始，用同样的方法确定第二个字母。

代码

---

class Solution(object):
    def removeDuplicateLetters(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 记录结果
        result = ''
        # 记录每个字母最后出现的位置
        lastpos = {}
        for i, c in enumerate(s):
            lastpos[c] = i
        # 对s中所有出现的字母进行排序
        order = sorted(list(set(s)))
        while len(order) > 0:
            # 按照字母表顺序判断result的下一个位置是哪个字母
            for i, c in enumerate(order):
                # 找出该字母在原字符串中出现的位置
                p = s.find(c)
                # 判断剩余的字母有没有只在p位置之前出现的
                if p <= min(lastpos.values()):
                    # 如果没有，则c就是下一个字母
                    result += c
                    order.pop(i)
                    del lastpos[c]
                    # 原字符串在c之前的部分用0代替，表示删除
                    s = '0' * p + s[p:]
                    break
        return result