C++ solution based on stack, o(n)


  • 0
    B
    class Solution {
    public:
        string removeDuplicateLetters(string s) {
            int letterCount[26];
            for (int i = 0; i < 26; i++) {
                letterCount[i] = 0;
            }
            int distinctCount = 0;
            for (char c : s) {
                int index = c - 'a';
                if (letterCount[index] == 0) {
                    distinctCount++;
                }
    
                letterCount[index] = letterCount[index] + 1;
            }
    
            vector<char> stack;
            stack.reserve(distinctCount);
            int existing[26];
            for (int i = 0; i < 26; i++) {
                existing[i] = 0;
            }
            for (char c : s) {
                int index = c - 'a';
                letterCount[index] = letterCount[index] - 1;
                if (existing[index] != 0) {           
                    continue;
                }
    
                if (stack.size() == 0) {
                    pushLetter(c, stack, existing, letterCount);
                    continue;
                }
    
                char top = stack.back();
                while (c < top && letterCount[top - 'a'] > 0)
                {
                    existing[top - 'a'] = 0;
                    stack.pop_back();
                    if (stack.size() == 0) {
                        break;
                    }
    
                    top = stack.back();
                }
    
                pushLetter(c, stack, existing, letterCount);
            }
    
            return string(stack.begin(), stack.end());
        }
    
        void pushLetter(char c, vector<char>& stack, int* existing, int* letterCount) {
            int index = c - 'a';
            stack.push_back(c);
            existing[index] = 1;
        }
    };
    

Log in to reply
 

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