O(n) time O(1) space complexity.


  • 0
    O

    Bitwise operation guys, goto code :)


    Using two integers and their bits to represent a letter (lsb is 'a', second lsb is 'b' etc..): wasFound indicates if a letter was found in the string and duplicateFound if it was found more than one time.

    First thing, we check the letters one by one, if it was found before we sit its bit in duplicateFound. Otherwise, we set its bit in the wasFound.

    After that, we iterate over the characters again, the first character we find with a set bit in wasFound and unset bit in duplicateFound we return it.

    int firstUniqChar(char* s) {
        if (s == NULL)
            return -1;
        
        char *str = s;
        int wasFound = 0, duplicateFound = 0, c;
    
        while (*str != '\0') {
            c = *str - 'a' ;
            if (wasFound & 1<<c) {
                duplicateFound |= 1<<c;
            } else {
                wasFound |= 1<<c;
            }
            str++;
        }
    
        str = s;
        while (*str != '\0') {
            c = *str - 'a' ;
            if ((wasFound & 1<<c) && !(duplicateFound & 1<<c)) {
                return str-s;
            }
            str++;
        }
        return -1;
    }
    

Log in to reply
 

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