316. Remove Duplicate Letters

Intuition

The problem requires us to remove duplicate letters from a string while maintaining the lexicographically smallest possible result. We need to ensure that:

1. Each character appears only once in the result
2. The relative order of characters is preserved
3. The result is lexicographically smallest among all possible results

Approach

1. First, we create a map lastSeen to record the last occurrence of each character in the string
2. We use a stack (st) to build our result and a set (seen) to track characters we've already included
3. For each character in the string:
   • If we haven't seen it before, we try to add it to our result
   • Before adding, we check if we can remove characters from the stack that are:
     • Greater than the current character (to maintain lexicographical order)
     • Will appear again later in the string (using lastSeen map)
4. Finally, we convert the stack to a string and return it

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Keywords

• Stack
• Greedy
• String
• Hash Map
• Lexicographical Order

Code

func removeDuplicateLetters(s string) string {
    lastSeen := make(map[rune]int)
    for i, c := range s {
        lastSeen[c] = i
    }

    st, seen := make([]rune, 0), make(map[rune]bool)
    for i, c := range s {
        if !seen[c] {
            for len(st) > 0 && c < st[len(st) - 1] && i < lastSeen[st[len(st) - 1]] {
                delete(seen, st[len(st) - 1])
                st = st[: len(st) - 1]
            }
            seen[c], st = true, append(st, c)
        }
    }

    return string(st)
}