SIMPLE, CLEAR, and FAST-3ms Iterative Solution. Don't Miss it :D


  • 0
    O
    • array last_pos stores last position of a letter in string
    • array inserted marks whether you have put the letter in stack
    • the stack st, tries best to maintain an ascending char sequence, UNLESS you have to insert a large letter which does not have a later occurrence.
    class Solution {
    public:
        string removeDuplicateLetters(string s) {
            vector<int> last_pos(26, 0);
            vector<bool> inserted(26, false);
            for (int i = 0; i < s.size(); i++)
                last_pos[s[i] - 'a'] = i;
            
            vector<char> st;
            for (int i = 0; i < s.size(); i++) 
                if (!inserted[s[i] - 'a']) {
                    while (!st.empty() && st.back() > s[i] && last_pos[st.back() - 'a'] > i) {
                        inserted[st.back() - 'a'] = false;
                        st.pop_back();
                    }
                    st.push_back(s[i]);
                    inserted[s[i]- 'a'] = true;
            }
            
            return string(st.begin(), st.end());
        }
    };
    

Log in to reply
 

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