刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/remove-duplicate-letters/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

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

示例 1：

输入：s = "bcabc"
输出："abc"

示例 2：

输入：s = "cbacdcbc"
输出："acdb"

提示：

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

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

思路

这道题跟402题类似，都可以考虑*单调栈*的思路，但是不同的是，每个字符有它自己的移除次数，即出现次数减一；此外就是对于本题中重复出现的字符来说，并非是402中如果不影响结果大小则可以直接放入结果，留待后续处理的处理方法，而是需要直接移除掉，因为后到的重复的字符，一定会增大结果的字典序大小，这一点可以画图穷举下或者反证一下。

那么到这里，代码结构就比较清晰了，一个是计数、一个是是否已经出现在结果集，其他的条件跟402没有什么区别了。

代码

func removeDuplicateLetters(s string) string {
	sBytes := []byte(s)
	byteCountMap := make(map[byte]int, len(s))
	hasByteMap := make(map[byte]int, len(s))
	for _, sByte := range sBytes {
		byteCountMap[sByte]++
		hasByteMap[sByte] = 0
	}

	var tempRes []byte
	for _, sByte := range sBytes {
		if hasByteMap[sByte] > 0 {
			byteCountMap[sByte]--
			continue
		}
		for len(tempRes) > 0 && byteCountMap[tempRes[len(tempRes)-1]] > 1 && sByte < tempRes[len(tempRes)-1] {
			byteCountMap[tempRes[len(tempRes)-1]]--
			hasByteMap[tempRes[len(tempRes)-1]]--
			tempRes = tempRes[:len(tempRes)-1]
		}
		tempRes = append(tempRes, sByte)
		hasByteMap[sByte]++
	}
	return string(tempRes)
}