C++ solution using stack [AC]


  • 0

    The idea is to use a stack to get the smallest lexicographical string when the duplicates are removed.

    We will first create a count of each alphabet in the string. If the character is already in the stack, we will skip it . When we encounter a never before seen character, we compare it with the top of the stack. If the current character is smaller than the stack top we will pop from the stack (if we are sure that the popped element will come again in the string) until current is greater.

    The reason behind this logic is we need the smallest lexicographical string, hence a smaller character should come before a larger one.

    In the end, the result is stored in the stack.

    class Solution {
    
    public:
        string removeDuplicateLetters(string s) {
            int n = s.length();
            string res="";
            stack<char> st;
            int count[26]={0};
            int vis[26]={0};
            memset(vis,0,sizeof(vis));
            //base case
            if(n==0 || n==1)
                return s;
            //create count of each alphabet
            for(int i=0;i<n;i++)
                count[s[i]-'a']++;
            
            for(int i=0;i<n;i++)
            {
                int curr = s[i]-'a';
                count[curr]--;
                
                if (vis[curr]) 
                    continue;
                
                while( !st.empty() && st.top()> s[i] && count[st.top()-'a'] > 0)
                {
                    vis[st.top()-'a']=0;
                    st.pop();
                }
                vis[curr]=1;
                st.push(s[i]);
            }
            while(!st.empty())
            { 
                res+=st.top();
                st.pop();
            }
            reverse(res.begin(),res.end());
            return res;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.