316. Remove Duplicate Letters

Medium

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 <= 104

• s consists of lowercase English letters.

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

解題

使用 stack 來記錄，並另外建立兩個陣列，一個紀錄字元是否已經被選中，另一個紀錄字元在 s 最後出現的位置。

func removeDuplicateLetters(s string) string {
    record := make([]bool, 26)
    lastTime := make([]int, 26)

    for i, c := range s {
        lastTime[c - 'a'] = i // 紀錄最後出現的位置
    }

    stack := make([]byte, 0)
    for i:=0; i<len(s); i++ {
        for {
            if len(stack) == 0 { // stack為空，無條件將字元推入
                stack = append(stack, s[i])
                record[s[i] - 'a'] = true // 將已經出現過改為 true
                break
            } 

            if record[s[i] - 'a'] { break } //目前遍歷的字元在前面已經出現了
        
            if stack[len(stack) - 1] < s[i] { // 如果stack最後一個字元比目前字元小
                stack = append(stack, s[i]) // 直接推入目前字元
                record[s[i] - 'a'] = true
                break
            } else if stack[len(stack) - 1] > s[i] { // 如果stack最後一個字元較大
                if i >= lastTime[stack[len(stack) - 1] - 'a']{ //如果stack最後一個字元後面將不會再遍歷到，不要拿掉它
                    stack = append(stack, s[i])
                    record[s[i] - 'a'] = true
                    break
                } else { // 將最後一個字元 pop 出來
                    record[stack[len(stack) - 1] - 'a'] = false // 更改最後一個字元的狀態
                    stack = stack[:len(stack)-1]
                }
            }
        }
        
    }

    return string(stack)
}