移除小写字母中重复的字母，让所有字母都只出现一次，并且结果是所有结果中按照字典序排序最小的那个。

Example 1

  • Input: “bcabc”
  • Output: “abc”

Example 2

  • Input: “cbacdcbc”
  • Output: “acdb”

解法之一:

  1. 通过一个数组对每一个出现的字母进行计数
  2. 遍历每一个字母放入栈，并将该字母的计数减 1
  3. 查看栈底的字母有没有比当前字母大且该字母的计数不为 0 的（有比当前更小的字典序），从栈底弹出该字母
func removeDuplicateLetters(s string) string {
	var countOfEachLetter [26]int
	var visited [26]bool
	stack := make([]byte, 0)
	stackBottom := 0

	bytesArr := []byte(s)

	for _, c := range bytesArr {
		countOfEachLetter[getIndex(c)]++
	}

	for _, c := range bytesArr {
		index := getIndex(c)
		countOfEachLetter[index]--
		if visited[index] {
			continue
		}

		// countOfEachLetter[getIndex(stack[stackBottom])] > 0 后面还有该字符
		for len(stack[stackBottom:]) > 0 && stack[stackBottom] > c && countOfEachLetter[getIndex(stack[stackBottom])] > 0 {
			// 标记为未访问用于后面的字符加入结果
			visited[getIndex(stack[stackBottom])] = false

			// 移动栈底
			stackBottom++
		}

		// 加入到结果栈
		stack = append(stack, c)
		visited[index] = true
	}
	return string(stack[stackBottom:])

}

func getIndex(b byte) int {
	return int(b - 'a')
}

通过上面解法遇到如下错误：

  • testcase: ‘“bbcaac”’
  • answer: “bca”
  • expected_answer: “bac”

经过一番排查不应该从栈底查找，应该从栈顶开始，通过的代码如下：

func removeDuplicateLetters(s string) string {
	var countOfEachLetter [26]int
	var visited [26]bool
	st := &stack{}

	bytesArr := []byte(s)

	for _, c := range bytesArr {
		countOfEachLetter[getIndex(c)]++
	}

	for _, c := range bytesArr {
		index := getIndex(c)
		countOfEachLetter[index]--
		if visited[index] {
			continue
		}

		// countOfEachLetter[getIndex(st.topChar())] > 0 后面还有该字符
		for !st.empty() && st.topChar() > c && countOfEachLetter[getIndex(st.topChar())] > 0 {
			// 标记为未访问用于后面的字符加入结果
			visited[getIndex(st.pop())] = false
		}

		// 加入到结果栈
		st.push(c)
		visited[index] = true
	}
	return st.String()
}

func getIndex(b byte) int {
	return int(b - 'a')
}

type stack struct {
	top    *stackItem
	bottom *stackItem
}

type stackItem struct {
	prev *stackItem
	next *stackItem
	c    byte
}

func (s *stack) topChar() byte {
	return s.top.c
}

// 从栈顶弹出
func (s *stack) pop() byte {
	top := s.top
	s.top = s.top.prev
	if top == s.bottom {
		s.bottom = s.top
	}
	return top.c
}

func (s *stack) push(c byte) {
	new := &stackItem{
		prev: s.top,
		c: c,
	}
	if s.bottom == nil {
		s.bottom = new
	}
	if s.top == nil {
		s.top = new
	} else {
		s.top.next = new
		s.top = new
	}
}


func (s *stack) empty() bool {
	return s.top == nil
}

func (s *stack) String() string {
	buf := make([]byte, 0, 10)
	current := s.bottom
	for current != nil {
		buf = append(buf, current.c)
		current = current.next
	}
	return string(buf)
}