return the first non repeating character in a string in javascript

Question

So I tried looking for this in the search but the closest I could come is a similar answer in several different languages, I would like to use Javascript to do it.

The problem is I have an arbitrary string that I would like to return the first non repeating character. EX: 'aba' -> would return b 'aabcbd' -> would return c. This is what I have so far, just a simple for loop to start.

var someString = 'aabcbd';



var firstNonRepeatedCharacter = function(string) {
for(var i = 0; i < someString.length; i++){

}
};

http://jsfiddle.net/w7F87/ Not sure where to go from here

Answer 1

function firstUniqChar(str) {
    let myMap = new Map();
    for(let i = 0; i < str.length; i++) {
        let char = str.charAt(i);
        if(!myMap.has(char)) {
            myMap.set(char, 0);
        }
        myMap.set(char, myMap.get(char) + 1 );
    }
    for(let [key, value] of myMap) {
       if(value === 1) {
           return key;
       }
    }
    return null;
}

let result = firstUniqChar("caabbdccee");
console.log(result);

You can use Map Object and set key and value, where in value you store the count for that particular character, After that you can iterate over map and check where is value 1 and return that key.

Map Object remembers the original insertion order of the keys.

Answer 2

If you're looking for the first occurrence of a letter that only occurs once, I would use another data structure to keep track of how many times each letter has been seen. This would let you do it with an O(n) rather than an O(n²) solution, except that n in this case is the larger of the difference between the smallest and largest character code or the length of the string and so not directly comparable.

Note: an earlier version of this used for-in - which in practice turns out to be incredibly slow. I've updated it to use the character codes as indexes to keep the look up as fast as possible. What we really need is a hash table but given the small values of N and the small, relative speed up, it's probably not worth it for this problem. In fact, you should prefer @Guffa's solution. I'm including mine only because I ended up learning a lot from it.

function firstNonRepeatedCharacter(string) {
   var counts = {};
   var i, minCode = 999999, maxCode = -1;
   for (i = 0; i < string.length; ++i) {
        var letter = string.charAt(i);
        var letterCode = string.charCodeAt(i);
       if (letterCode < minCode) {
           minCode = letterCode;
       }
       if (letterCode > maxCode) {
           maxCode = letterCode;
       }
        var count = counts[letterCode];
        if (count) {
           count.count = count.count + 1;
        }
        else {
            counts[letterCode] = { letter: letter, count: 1, index: i };
        }
   }

    var smallestIndex = string.length;
    for (i = minCode; i <= maxCode; ++i) {
       var count = counts[i];
       if (count && count.count === 1 && count.index < smallestIndex) {
          smallestIndex = count.index;
       }
   }

    return smallestIndex < string.length ? string.charAt(smallestIndex) : '';
}

See fiddle at http://jsfiddle.net/b2dE4/

Also a (slightly different than the comments) performance test at http://jsperf.com/24793051/2