Remove Duplicate Letters — Greedy Monotonic Stack

Problem

Remove duplicate letters so each appears once, result is the smallest in lexicographic order.

Approach — Greedy Stack

Track last_occurrence of each character. For each char:

If already in stack, skip
Pop stack top if it's larger AND appears later in string (can reuse)
Push current character

Time: O(n) | Space: O(26)

Solutions

Python

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        last={c:i for i,c in enumerate(s)}
        stack=[]; seen=set()
        for i,c in enumerate(s):
            if c in seen: continue
            while stack and c<stack[-1] and last[stack[-1]]>i:
                seen.discard(stack.pop())
            stack.append(c); seen.add(c)
        return ''.join(stack)

C++

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

Complexity

Time: O(n) | Space: O(26) = O(1)