key-indexed symbol table and two pointer


  • 0
    N

    Time Complexity: O(n)
    Space Complexity: O(n)

    class Solution {
    public:
        int firstUniqChar(string s) {
            vector<int> table(26, 0);
            int i;
            for (i = 0; i < s.length(); i++) {
                table[s[i] - 'a']++;
            }
            
            for (i = 0; i < s.length(); i++) {
                if (table[s[i] - 'a'] == 1) {
                    return i;
                }
            }
            
            return -1;
        }
    };
    

    2 optimization
    Although above methods time complexity is O(n), however it needs to scan string twice. So practical application may not be good.
    We can use two pointer + symbol table to do one pass.

    class Solution {
    public:
        int firstUniqChar(string s) {
            vector<int> table(26, 0);
            int i, j = 0, len = s.length() ;
            if (len == 0) return -1;
            
            for (i = 0; i < len; i++) {
                table[s[i] - 'a']++;
                if (table[s[i] - 'a'] > 1) {
                    while (j < len && table[s[j] - 'a'] > 1) {
                        j++;
                    }
                    
                    if (j == len)
                        return -1;
                }
            }
    
            return j;
        }
    };
    

Log in to reply
 

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