Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.3 kB
1
Indexable
Never
class Solution {
public:
    string removeDuplicateLetters(string str) {
        stack<char>s;
        int maxsize=INT_MIN;
        unordered_map<char,int> fre; // both contain 0 and false initially
        unordered_map<char,bool> pres;
        for(auto i:str){
            fre[i]++;
        }

        for(auto i:str){                     //.. //fre[i]-- must come befoer continue as we must always do it even if its present to decrease frequency
            fre[i]--;                            //as we are iterating over the string , it wont come again and we lose it by 1
            if(pres[i]) continue;                //char already present in stack(result), go to next character
            while(!s.empty() && s.top()>i && fre[s.top()]>0){   //we will pop stack until top of stack is less than i or the element at top of stack doesnt occur again
                                                   
                pres[s.top()]=false;                                      //we are popping it
                s.pop();
            } 
            s.push(i);
            pres[i]=true;   
        }

        string res;
        while(!s.empty()){
            res=s.top()+res;
            s.pop();
        }
        return res;

    }
};