算法随笔_30: 去除重复字母
上一篇:算法随笔_29:最大宽度坡_方法3-CSDN博客
=====
题目描述如下:
给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1：
输入：s = "bcabc"输出"abc"
=====
算法思路:
首先我们考虑第一个条件: 如何去掉字符串中重复的字母？这个比较简单。我们可以新开辟一个同样长度的新数组s_new来存储最后的结果。然后我们从左往右遍历原数组，依次把字符放入新数组s_new中。并判断即将放入的字符在新数组当中是否已经出现，如果出现，则不放入字符。最终得到的就是去掉重复字符之后的新的字符串。在代码实现的时候可能会有一些细节需要考虑，比如说，s_new数组后面可能会出现未填满的情况，但这属于细节问题，在代码实现中可以用各种办法解决它，同时也不会影响时间复杂度。
现在让我们来看第二个条件: 最终答案需要取字典序最小的字符串。比如，示例1中有两种可能的符合去重条件的答案: bca, abc。同样都是去掉重复字符之后的字符串，但字典序最小的字符串是abc。
因此，在上面的算法中，当发现放入的字符比如: c，在新数组中已经出现时，我们需要一个算法来判断如何进行重复字符的取舍问题。是保留已经在数组中的字符c，还是需要删除它，放入后面的字符c。
我们拿上面的例子做进一步的分析。bcabc，我们从左向右枚举原字符串，当枚举到第二个b时，如果删除最后一个b，那么字符串就变成bca。删除第一个b，字符串就变成了cab。我们发现只要b的后面的字符是大于b的，肯定要删除第二次出现的重复字母。因为如果删除了第一次出现的字符b，字符c就前移一位，不管后面的字符串是什么样的，以字符c开始引领的字符串必然大于以字符b开始引领的同样长度的字符串。
与上面的情况类似，如果b的后面的字符是小于b的字符，那需要删除第一个字符b。比如bab，最后的结果应该是ab。
因此，我们发现的特征就是:
如果s[i]>s[i+1]，且s[i]这个字符出现2次及以上时，我们需要删除这个字符s[i]。
此时注意一下，当删除s[i]之后，s[i+1]移到了s[i]这个位置，新的排列仍然需要保持这个特征。即，如果s[i-1]仍然大于s[i+1]，且s[i-1]这个字符出现2次及以上时，我们仍需要删除这个字符s[i-1]，s[i+1]需要继续前移。
还是用上面的例子说明，当我们尝试放入s_new时，有如下步骤:
- 放入b
- 因为c大于b，所以放入c
- 因为a小于c，且c出现2次，删除c
- a继续和b比较，a小于b，且b出现2次，删除b。前面已经没有可以删除的字符，放入a。
- 因为b大于a，所以放入b
- 因为c大于b，所以放入c，至此完成。
这里有一些细节还需要说明一下。
1. 假如原字符很长，abc后面还有其他字符，且abc每个字符后面都还出现多次以上。仍然需要按照上面的规律来放入s_new。
2. 只出现1次的字符，必须保留。比如上面的例子，如果没有第二次出现的字符c。需要依次放入bca，然后舍弃第二个b。因为字符c不能删除，所以字符a就无需依次和前面的比较了。
3. 即将放入的字符如果在s_new中已经存在，则不能放入。
我们发现s_new中的字符有个特点，除了那些只出现1次的字符，出现2次及以上的字符都是按字典序增大的，然后碰到小于的字符在一个一个删除。这很像一个栈的数据结构。先递增入栈，在依据条件出栈。
经过上面一系列的分析，我们大体了解了整个的算法思路。下面我们来给出详细的算法:
1. 初始ch2cnt数组，共26个元素。我们用每个字母与字母a的ascii码的差值来做为数组的索引。初始元素值为0。遍历一遍原字符串，相同字母每出现一次，ch2cnt相应的元素值加1。统计出每个字母出现的次数。
2. 初始putted数组，也是26个元素。用每个字母与字母a的ascii码的差值来做为数组的索引。元素值为1表示此字母在s_new中已经存在，0表示不存在。然后把原字符串s中第一个字符在putted中对应的元素置为1。设置此数组的目的是为了更高效的查询s_new中已存在的字符，仅有O(1) 的时间复杂度。
3. 设s_new数组为最终的字符串数组。初始化时放入原字符串s的第一个字符。
4. 从第二个字符开始，从左向右枚举原字符串s。
5. 通过putted，判断当前字符s[i]是否在s_new中已经存在。如果存在，不放入s_new，且在ch2cnt中对应字符的次数减1。转到步骤4继续。如果不存在，转到下一步。
5. 从右往左枚举s_new数组，让s[i]依次与s_new数组的字符j比较，如果s[i]<=s_new[j]且字符j出现的次数大于1，我们去掉s_new的最后一个字符。循环步骤5，直到退出循环，然后我们把s[i]放入s_new。
其他一些细节详见代码。下面是代码实现:
class Solution(object):
def removeDuplicateLetters(self, s):
"""
:type s: str
:rtype: str
"""
ord_a=ord('a')
ch2cnt=[]
putted=[]
for i in range(26):
ch2cnt.append(0)
putted.append(0)
for ch in s:
ch2cnt[ord(ch)-ord_a]+=1
s_len=len(s)
s_new=[s[0]]
putted[ord(s[0])-ord_a]=1
for i in range(1,s_len):
ord_si=ord(s[i])-ord_a
if putted[ord_si]==1:
ch2cnt[ord_si]-=1
continue
j=len(s_new)-1
while j>=0 and s[i]<=s_new[j] and ch2cnt[ord(s_new[j])-ord_a]>1:
ch2cnt[ord(s_new[j])-ord_a]-=1
putted[ord(s_new[j])-ord_a]=0
s_new.pop()
j-=1
s_new.append(s[i])
putted[ord_si]=1
res=''.join(s_new)
return res
此算法的时间复杂度为O(n) 。