Problem Statement

Given a string, find the first non-repeating character in it and return it's index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode",
return 2.

Note: You may assume the string contain only lowercase letters.

Solutions

version 1

The first idea came to my mind is using double loops to check the Repeatability of every single charator. And I also used a dynamic allocated arrary to store whether every charator is duplicated.

int firstUniqChar(char* s) {
    int len = strlen(s);
     if (len == 1)
        return 0;

    int * status = (int*)malloc(len*sizeof(int));
    memset(status, 0, len*sizeof(int));
    int i;
    int j;

    for (i = 0; i < len - 1; i++) {
        bool has_repeat = false;
        if (status[i] == 1)
            continue;
        for (j = i + 1; j < len; j++) {
            if (s[i] == s[j]) {
                status[j] = 1;
                has_repeat =true;
            }
        }
        
        if (!has_repeat) {
            free(status);
            return i;
        }
            
    }
    
    free(status);
    return -1;
}

It is accepted successfully, but the performance is not ideal. Because it's time complexity is . I think it has the solution definitely.

Version 2

Instead of the allocated array with the string's length, the letter table with 26 letters is enough for this scenario:

int firstUniqChar(char* s) {
    int len = strlen(s);

    int * alphaTable = (int *)malloc(26*sizeof(int));
    memset(alphaTable, 0, 26*sizeof(int));
    int i;

    for (i = 0; i < len; i++) {
        alphaTable[s[i] - 'a']++;
    }

    for (i = 0; i < len; i++) {
        if (alphaTable[s[i] - 'a'] == 1) {
            free(alphaTable);
            return i;
        }
    }

    free(alphaTable);
    return -1;
}

References

https://leetcode.com/problems/first-unique-character-in-a-string/description