LeetCode 1081. Smallest Subsequence of Distinct Characters

Question

Given a string s, return the lexicographically smallest subsequence of s that contains all the distinct characters of s exactly once.

https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

class Solution {
    public String smallestSubsequence(String s) {
        Stack<Integer> stack = new Stack<>();
        int[] last = new int[128];
        Set<Integer> visited = new HashSet<>();
        for (int i = 0; i < s.length(); i++) last[s.charAt(i)] = i;
        for (int i = 0; i < s.length(); i++){
            int c = s.charAt(i);
            if (!visited.add(c)) continue;
            while (!stack.isEmpty() && c < stack.peek() && i < last[stack.peek()]) visited.remove(stack.pop());
            stack.push(c);
        }
        StringBuilder sb = new StringBuilder();
        for (int i : stack) sb.append((char)(i));
        return sb.toString();
    }
}

Time complexity: O(n)

Space complexity: O(n)