316.Remove_Duplicate_Letters(Medium).md

316. Remove Duplicate Letters (Medium)

Date and Time: Apr 29, 2025

Link: https://leetcode.com/problems/remove-duplicate-letters

Walk-through:

1. Use a hashmap to record each letter's last occurrence.

2. Loop over each letter in s, for each letter s[i], if s[i] not in visited we can continue, if stack[] is not empty, we compare current letter s[i] with the top of stack, if s[i] < stack[-1] and the index of stack[-1] is not the last occurrence of this letter stack[-1], we should pop the top of element, because we should find the lexicographically smallest order. Also, we use visited() set to keep track of the letters in stack, when we remove this letter, we should also remove from visited(). Lastly, add this s[i] into stack[], visited().

Python:

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # Q: Return the lexicographically smallest subsequence
        # S: 1. Find each letter's last occurrence
        # 2. For each s[i], if s[i] is visited: we should skip. Otherwise, if stack is not empty, compare it with the top of stack, if s[i] < stack[-1] and stack[-1] is not the last occurrence of this letter. We can pop the top of stack. Then add s[i] into stack
        # TC: O(n), n=len(s), SC: O(1)

        # 1. Find each letter's last occurrence
        last_visit = {}
        for i in range(len(s)):
            last_visit[s[i]] = i
        # 2. Find the smallest lexicographical order
        stack = []
        visited = set()
        for i in range(len(s)):
            if s[i] not in visited:
                # Compare s[i] with stack[-1] and check the index of stack[-1] is the last or not
                while stack and s[i] < stack[-1] and i < last_visit.get(stack[-1], -1):
                    visited.remove(stack.pop())
                # Add s[i] into stack and visited
                stack.append(s[i])
                visited.add(s[i])
        return "".join(stack)

        # last_visit = {a:2, b:6, c:7, d:4}
        # stack = [a,c,d,b], visited = [a,c,d,b], i = 7

Time Complexity: $O(n)$
Space Complexity: $O(1)$, the space complexity will be at most max(len(s), 26)

Java

class Solution {
    /* 
    1. Record each letter's last occurrence index
    2. For each s[i], if s[i] not in visited, compare it with stack[-1], and stack[-1]'s last occurrence index
    3. If stack[-1] > s[i], and stack[-1] will appear later, remove from visited set() and stack
    4. Add s[i] into visited() and stack[]
    TC: O(n), n=len(s), SC: O(n)
    */
    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();
        Set<Character> visited = new HashSet<>();
        Map<Character, Integer> hashmap = new HashMap<>();

        // 1. Record each letter's last occurrence index
        for (int i=0; i < s.length(); i++) {
            hashmap.put(s.charAt(i), i);
        }
        // 2. Loop over s[i] and compare with stack[]
        for (int i=0; i < s.length(); i++) {
            if (!visited.contains(s.charAt(i))) {
                // Compare s[i] with stack[-1], and stack[-1] appears later
                while (!stack.empty() && s.charAt(i) < stack.peek() && hashmap.get(stack.peek()) > i) {
                   visited.remove(stack.pop());
                }
                visited.add(s.charAt(i));
                stack.push(s.charAt(i));
            }
        }
        // Concatenate chars from stack[] to string
        StringBuilder sb = new StringBuilder();
        while (!stack.empty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
}