Better than O(2n) C solution if n > 26 (9ms - beats 58.92%)


  • 0
    A

    You don't need to iterate the second loop for the entire length of the string (which could b >> 26), you only have to iterate through the hash map which is 26 iterations in the worst case.

    int firstUniqChar(char* s) {
        int map[26][2] = {{0,0}};
        int len = strlen(s);
        int i, index = len;
    
        if (!s || len == 0) {
            return -1;
        }
        
        for (i = 0; i < len; i++) {
            map[s[i]-'a'][0]++;
            map[s[i]-'a'][1] = i;
        }
    
        for (i = 0; i < 26; i++) {
            if (map[i][0] == 1) {
                if (map[i][1] < index) {
                    index = map[i][1];
                }
            }
        }
        
        if (index == len) {
            return -1;
        }
        
        return index;
    }
    

Log in to reply
 

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