C++ 39 ms w/ Queue (90%)


  • 0
    A

    This solution uses a queue and an array instead of a hash table to keep track of the characters by their ascii representation. Using a queue allows use to determine the first "unique" character. With a queue (FIFO; First In First Out), we can do this quite nicely. Computing the index into the "repeat" array by subtracting '0' is an optimization that the compiler would do otherwise.

    class Solution {
    public:
        int firstUniqChar(string s) {
            int repeat[256] = {0};
            queue<int> order;
            for(int i=0; i<s.size(); ++i) {
                int index = s[i] - '0';
                ++repeat[index];
                if(repeat[index] == 1)
                    order.push(i);
            }
            while(!order.empty() && repeat[s[order.front()]-'0'] > 1)
                order.pop();        
            return !order.empty()? order.front(): -1;
        }
    };
    

Log in to reply
 

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