文章目录

• 一、题目内容
• 二、解题思路
• 三、代码

---

一、题目内容

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同

示例 1：
输入：s = “bcabc”
输出："abc"

示例 2：
输入：s = “cbacdcbc”
输出："acdb"

提示：
1 <= s.length <= 104
s 由小写英文字母组成

二、解题思路

每次查找字符在s中最后出现的位置，并找到最小值，这样的话就知道哪个字母出现次数少，并且从这个最小位置往前找最小的字母，把它添加到结果集里，然后从这个最小字母后所有和这个字母一样的字符都删除了， 然后在剩下的s中再按照这样的方法找即可。

例如：s = “cbacdcb”
1.s_index: [7, 6, 2, 7, 4, 7, 6, 7]
location: 2
位置2之前的字符串"cba"中最小的字母是’a’
res: a
删除最小字母后的字符串: cdcbc

2.s_index: [4, 1, 4, 3, 4]
location: 1
位置1之前的字符串"cd"中最小的字母是’c’
res: ac
删除最小字母后的字符串: db

3.s_index: [0, 1]
location: 0
位置0之前的字符串"d"中最小的字母是’d’
res: acd
删除最小字母后的字符串: b

4.s_index: [0]
location: 0
位置0之前的字符串"b"中最小的字母是’b’
res: acdb
删除最小字母后的字符串:

因此res是acbd

三、代码

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        res = ""

        while s:
            s_index = list(map(s.rindex, s))
            location = min(s_index)
            before_location_min = min(s[:location + 1])
            res += before_location_min
            s = s[s.index(before_location_min):].replace(before_location_min, "")

        return res



if __name__ == '__main__':
    ss = "cbacdcbc"
    s = Solution()
    ans = s.removeDuplicateLetters(ss)
    print(ans)