316. Remove Duplicate Letters #

Problem #

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

Constraints:

1 <= s.length <= 10^4
s consists of lowercase English letters.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

Code #

package leetcode

// Solution 1: Greedy + monotonic stack. Keep only one of each letter, and the result has the smallest lexicographical order among all feasible solutions.
// Use last to record the last occurrence index of each letter; when traversing, if the current character is smaller than the stack top, and the stack-top character will still
// appear again later, pop the stack top, so as to make the result as small as possible. Time complexity O(n), space complexity O(1) (26 letters).
func removeDuplicateLetters(s string) string {
	var last [26]int
	for i := 0; i < len(s); i++ {
		last[s[i]-'a'] = i
	}
	var inStack [26]bool
	stack := []byte{}
	for i := 0; i < len(s); i++ {
		c := s[i]
		if inStack[c-'a'] {
			continue
		}
		for len(stack) > 0 && stack[len(stack)-1] > c && last[stack[len(stack)-1]-'a'] > i {
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			inStack[top-'a'] = false
		}
		stack = append(stack, c)
		inStack[c-'a'] = true
	}
	return string(stack)
}