Remove Duplicate Letters

class Solution {
public:
    string removeDuplicateLetters(string s) {
        int cnt[26] = {0};
        bool seen[26] = {false};
        for (char c : s) cnt[c - 'a']++;
        string st;
        for (char c : s) {
            cnt[c - 'a']--;
            if (seen[c - 'a']) continue;
            while (!st.empty() && st.back() > c && cnt[st.back() - 'a'] > 0) {
                seen[st.back() - 'a'] = false;
                st.pop_back();
            }
            st.push_back(c);
            seen[c - 'a'] = true;
        }
        return st;
    }
};

func removeDuplicateLetters(s string) string {
    var cnt [26]int
    var seen [26]bool
    for i := 0; i < len(s); i++ {
        cnt[s[i]-'a']++
    }
    st := []byte{}
    for i := 0; i < len(s); i++ {
        c := s[i]
        cnt[c-'a']--
        if seen[c-'a'] {
            continue
        }
        for len(st) > 0 && st[len(st)-1] > c && cnt[st[len(st)-1]-'a'] > 0 {
            seen[st[len(st)-1]-'a'] = false
            st = st[:len(st)-1]
        }
        st = append(st, c)
        seen[c-'a'] = true
    }
    return string(st)
}

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        cnt = [0] * 26
        seen = [False] * 26
        for c in s:
            cnt[ord(c) - ord('a')] += 1
        st: list[str] = []
        for c in s:
            cnt[ord(c) - ord('a')] -= 1
            if seen[ord(c) - ord('a')]:
                continue
            while st and st[-1] > c and cnt[ord(st[-1]) - ord('a')] > 0:
                seen[ord(st[-1]) - ord('a')] = False
                st.pop()
            st.append(c)
            seen[ord(c) - ord('a')] = True
        return ''.join(st)

function removeDuplicateLetters(s) {
    const cnt = new Array(26).fill(0);
    const seen = new Array(26).fill(false);
    const A = 'a'.charCodeAt(0);
    for (const c of s) cnt[c.charCodeAt(0) - A]++;
    const st = [];
    for (const c of s) {
        const idx = c.charCodeAt(0) - A;
        cnt[idx]--;
        if (seen[idx]) continue;
        while (st.length && st[st.length - 1] > c && cnt[st[st.length - 1].charCodeAt(0) - A] > 0) {
            seen[st[st.length - 1].charCodeAt(0) - A] = false;
            st.pop();
        }
        st.push(c);
        seen[idx] = true;
    }
    return st.join('');
}

class Solution {
    public String removeDuplicateLetters(String s) {
        int[] cnt = new int[26];
        boolean[] seen = new boolean[26];
        for (int i = 0; i < s.length(); i++) cnt[s.charAt(i) - 'a']++;
        StringBuilder st = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            cnt[c - 'a']--;
            if (seen[c - 'a']) continue;
            while (st.length() > 0 && st.charAt(st.length() - 1) > c && cnt[st.charAt(st.length() - 1) - 'a'] > 0) {
                seen[st.charAt(st.length() - 1) - 'a'] = false;
                st.deleteCharAt(st.length() - 1);
            }
            st.append(c);
            seen[c - 'a'] = true;
        }
        return st.toString();
    }
}

function removeDuplicateLetters(s: string): string {
    const cnt: number[] = new Array<number>(26).fill(0);
    const seen: boolean[] = new Array<boolean>(26).fill(false);
    const A = 'a'.charCodeAt(0);
    for (const c of s) cnt[c.charCodeAt(0) - A]++;
    const st: string[] = [];
    for (const c of s) {
        const idx = c.charCodeAt(0) - A;
        cnt[idx]--;
        if (seen[idx]) continue;
        while (st.length && st[st.length - 1] > c && cnt[st[st.length - 1].charCodeAt(0) - A] > 0) {
            seen[st[st.length - 1].charCodeAt(0) - A] = false;
            st.pop();
        }
        st.push(c);
        seen[idx] = true;
    }
    return st.join('');
}