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.
Given "bcabc"
Return "abc"
Given "cbacdcbc"
Return "acdb"
删除字符串里的重复字符,要让字母按字典顺序排序,前提是不能打乱之前的顺序。
代码:
解题思路:定义两个hash表,一个用来存储出现字符的个数,一个用来存储字符是否出现在结果中。然后遍历字符串,将对应字符个数减一,判断该字符串是否出现在结果中,如果出现在结果中,表明该字符串已经被放到了正确的位置上,则循环继续;如果没有出现在结果中,比较当前和结果的最后一个字符串,如果当前的字符串小于result的back的话,并且结果字符串的最后一个字符在后边还会出现,那么我们就把结果的最后一个字符串踢出,到这里我们是要保证小的字符串放到前边,也要保证大的字符串在后边还会出现;如果当前的字符串大于结果的字符串,或者结果字符串尾部字符已经是最后一个,那么我们就直接把当前遍历的字符串加在结果的尾部,并且将inresult设置为true,表示这个字符串已经出现在result里。为了使第一次比较成功,我们需要把result初始化成" ",如果result时空的话就没法去出它的最后一个数值。