题目

给你一个仅包含小写字母的字符串，请你去除字符串中重复的字母，使得每个字母只出现一次。

需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1:输入: "bcabc" 输出: "abc"

示例 2:输入: "cbacdcbc" 输出: "acdb"

注意：该题与 1081

https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同

解题思路分析

1、单调栈；时间复杂度O(n)，空间复杂度O(n)

func removeDuplicateLetters(s string) string {
	stack := make([]byte, 0)
	arr := [256]byte{}
	m := make(map[byte]bool)
	for i := 0; i < len(s); i++ {
		arr[s[i]]++
	}
	for i := 0; i < len(s); i++ {
		if m[s[i]] == true {
			arr[s[i]]--
			continue
		}
		// arr[栈顶]说明有重复元素
		// 栈顶>s[i]:说明字典序不满足
		for len(stack) > 0 && stack[len(stack)-1] > s[i] && arr[stack[len(stack)-1]] > 0 {
			m[stack[len(stack)-1]] = false
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, s[i])
		arr[s[i]]--
		m[s[i]] = true
	}
	return string(stack)
}

2、递归；时间复杂度O(n)，空间复杂度O(n)

func removeDuplicateLetters(s string) string {
	arr := [26]int{}
	pos := 0
	for i := 0; i < len(s); i++ {
		arr[s[i]-'a']++
	}
	for i := 0; i < len(s); i++ {
		if s[i] < s[pos] {
			pos = i
		}
		arr[s[i]-'a']--
		if arr[s[i]-'a'] == 0 {
			break
		}
	}
	if len(s) == 0 {
		return ""
	}
	newStr := strings.ReplaceAll(s[pos+1:], string(s[pos]), "")
	return string(s[pos]) + removeDuplicateLetters(newStr)
}

总结

Hard题目，题目可以使用单调栈来处理字典序