Iterative c++ solution


  • 0
    A
    class Solution{
        private:
        bool condition(const string s, const vector<char> unique_letters, const size_t found, const size_t index){
            //True if one can insert charachter unique_letters[index] and the rest of the characters unique_letters[index+1:end]
            //are in the right side of s
            for (size_t i = index+1; i < unique_letters.size(); ++i){
                if (s.find_first_of(unique_letters[i], found+1) == string::npos){
                    // the i-th letter of unique_letters is not on the right of s[found]
                    return false;
                }
            }
           // All of the remaning characters are on right of found
            return true;
        }
        public:
        string removeDuplicateLetters(string s) {
            //Find the unique character of the string s ordered
            vector<char> unique_letters(s.begin(),s.end());
            sort(unique_letters.begin(), unique_letters.end());
            auto it = unique(unique_letters.begin(), unique_letters.end());
            unique_letters.resize(distance(unique_letters.begin(), it));
            //Find the smallest in lexicographical order
            size_t index = 0; // Current position in unique_letters
            size_t pos = 0;   // Current position in string s
            size_t alternatives = 0; // alternative to exchange with index
            while(index < unique_letters.size()){
                size_t found = s.find_first_of(unique_letters[index], pos);
                if ( condition( s, unique_letters, found, index) ){
                    // All of the remaning characters are on right of found
                    alternatives = index++;
                    pos = found;
                }
                else{
                    // Use another characters as alternative
                    swap(unique_letters[index], unique_letters[++alternatives]);
                }
            }
            // To string 
            return string(unique_letters.begin(),unique_letters.end());
        }
    };
    

Log in to reply
 

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