一、题目内容

给你一个字符串 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)

  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/111468506