题解#去除重复字母#

'''
解题思路：
1、输出out为最小字典排列的字符串，如新字符已在out中，则直接跳过
2、如新字符si不在out中，但小于out[-1]（不是字典序），检查后面是否还有out[-1]，如有则删除当前out[-1]；
   该过程通过while循环一直向前，直到while条件不满足
'''

class Solution:
    def removeDuplicateLetters(self, s):

        s = list(s)
        print('s=',s)
        n = len(s)

        out = [s[0]]
        for i in range(1,n):
            si = s[i]
            # 1、输出out为最小字典排列的字符串，如新字符已在out中，则直接跳过
            if si in out:
                continue
            # 2、如新字符si不在out中，但小于out[-1]（不是字典序），检查后面是否还有out[-1]，如有则删除当前out[-1]；
            # 该过程通过while循环一直向前，直到while条件不满足
            while out and si<out[-1] and out[-1] in s[i+1:]:
                out.pop()
            out.append(si)
            print('i=',i,'out=',out)

        return ''.join(out)

# s = 'cbacdcbc'  # acdb
s = "bcabc"  # abc
s = "abacb" # abc
t = Solution().removeDuplicateLetters(s)
print(t)