C++ O(n) iterative solution


  • 0
    H
    class Solution {
    public:
        string removeDuplicateLetters(string s) {
            const int kAdded = INT_MAX;
            vector<int> count(256, 0);
            for (char c : s) {
                ++count[c];
            }
            
            string ret;
            int begin = 0;
            int end;
            while (begin < s.size()) {
                if (count[s[begin]] == kAdded) {
                    ++begin;
                    continue;
                }
                
                end = begin;
                char min_c = s[end];
                int c_pos = end;
                while (end < s.size() && count[s[end]] > 1) {
                    if (count[s[end]] != kAdded) {
                        if (s[end] < min_c) {
                            min_c = s[end];
                            c_pos = end;
                        }
                        --count[s[end]];
                    }
                    ++end;
                }
                
                // all charaters in s[begin:end] should be removed, since
                // 1. they are removable.
                // 2. s[end] smaller than all of them.
                if (end < s.size() && s[end] < min_c) {
                    begin = end;
                    continue;
                }
                
                // restore count[c_pos + 1:end]
                for (int i = c_pos + 1; i < end; ++i) {
                    if (count[s[i]] == kAdded) {
                        continue;
                    }
                    ++count[s[i]];
                }
                count[min_c] = kAdded;
                begin = c_pos + 1;
                ret.push_back(min_c);
            }
            return ret;
        }
    };

Log in to reply
 

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