1081. Smallest Subsequence of Distinct Characters

import java.util.*;
class Solution {
    public String smallestSubsequence(String s) {
        int[] last = new int[26];
        boolean[] used = new boolean[26];
        for (int i = 0; i < s.length(); i++) {
            last[s.charAt(i) - 'a'] = i;
        }
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (used[c - 'a']) continue;
            while (!stack.isEmpty()
                    && stack.peekLast() > c
                    && last[stack.peekLast() - 'a'] > i) {
                used[stack.pollLast() - 'a'] = false;
            }
            stack.offerLast(c);
            used[c - 'a'] = true;
        }
        StringBuilder ans = new StringBuilder();
        while (!stack.isEmpty()) {
            ans.append(stack.pollFirst());
        }
        return ans.toString();
    }
}

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        last = {c: i for i, c in enumerate(s)}
        used = set()
        stack = []

        for i, c in enumerate(s):
            if c in used:
                continue

            while stack and stack[-1] > c and last[stack[-1]] > i:
                used.remove(stack.pop())

            stack.append(c)
            used.add(c)

        return "".join(stack)

class Solution {
public:
    string smallestSubsequence(string s) {
        vector<int> last(26);
        vector<bool> used(26, false);

        for (int i = 0; i < s.size(); i++)
            last[s[i] - 'a'] = i;

        string st;

        for (int i = 0; i < s.size(); i++) {
            char c = s[i];

            if (used[c - 'a']) continue;

            while (!st.empty() && st.back() > c &&
                   last[st.back() - 'a'] > i) {
                used[st.back() - 'a'] = false;
                st.pop_back();
            }

            st.push_back(c);
            used[c - 'a'] = true;
        }

        return st;
    }
};

var smallestSubsequence = function(s) {
    const last = new Array(26).fill(0);
    const used = new Array(26).fill(false);

    for (let i = 0; i < s.length; i++) {
        last[s.charCodeAt(i) - 97] = i;
    }

    const stack = [];

    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        const idx = c.charCodeAt(0) - 97;

        if (used[idx]) continue;

        while (
            stack.length &&
            stack[stack.length - 1] > c &&
            last[stack[stack.length - 1].charCodeAt(0) - 97] > i
        ) {
            used[stack.pop().charCodeAt(0) - 97] = false;
        }

        stack.push(c);
        used[idx] = true;
    }

    return stack.join("");
};