First Unique Character in a String#

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

Example#

Solution#

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    const hashTable = Object.create(null);
    Array.prototype.forEach.call(s, v => {
        if(hashTable[v] === void 0) hashTable[v] = 1;
        else ++hashTable[v];
    })
    const n = s.length;
    for(let i=0;i<n;++i){
        if(hashTable[s[i]] === 1) return i;
    }
    return -1;
};

Idea#

We can traverse the string twice. During the first traversal, we use a hash map to count the number of occurrences of each character in the string. During the second traversal, we return the index of the first character that occurs only once. If no such character is found, we return -1. Of course, we use a hash table for storage here. It might be faster to use two arrays for storage. The hash table needs to calculate HashCode and then obtain the index according to HashCode. When the string is longer, it may cause the underlying data of the Hash table to be reallocated, thereby generating a ReHash. Collision in Hash should also be considered. First, create a hash table, directly construct an object without a prototype, and then use the forEach method of the array to loop through the string to build the hash table. When the key does not exist, set the value of this key to 1, otherwise, increment the value. Then get the length of the string, and establish a loop. If the value of this key in the hash table is 1, the index of this value is returned. If not found, -1 is returned.

Daily Problem#

Reference#