Write a function to find the first non-repeated character in a string

Here is a practice question I am solving:


Write a function to find the first non-repeated character in a string.
For instance, the first non-repeated character in 'total' is 'o' and
the first non-repeated character in 'teeter' is 'r'.

How can I improve the efficiency of this algorithm?

function repeater(string){
    var charCount = {};
    for(var i = 0; i < string.length; i++){
        if(charCount[string[i]]){
            charCount[string[i]] = 'More Than One';
        } else {
            charCount[string[i]] = 'One Time';
        }
    }    
    for(var j = 0; j < string.length; j++){
        if(charCount[string[j]] === 'One Time'){
          return string.charAt(j);      
        }
    }

    return 'Everything is repeated';
}

http://repl.it/QUf/1

I also solved this using a nested loop:

var nonRepeater = function(str) {
  var index = [];
  var count;
  str.split('').forEach(function(letter, i) {
    count = 0;
    str.split('').forEach(function(latter) {
      if (letter === latter) {
        count += 1;
      }
    });
    index.push(count);
  });
//   console.log(index.indexOf(1));
  return str[index.indexOf(1)];
};

http://repl.it/QVI/2

I am trying to find a way to increase the efficiency of this algorithm. I am toying with ways to use a RegEx.

Does anyone know how to write this more efficiently in JavaScript? I have found a few guides in C but I do not know the language well.

After playing a lot with jsperf and having to admit that the regex solution is actually faster, which annoys me.

-
Your first approach is far superior than your second approach (O(2n) -> O(n^2)) as per Venu

-
you should cache string.length, looking up the value of a property slows things down

for(var i = 0, length = string.length; i < length; i++){

-
You can assign More than one and One time with a ternary, also you should cache string[i] and not look it up 3 times:

charCount[c] = charCount[c] ? 'More Than One' : 'One Time';

-
You do not need var j, just use i again

-
You used string[i] everywhere else, your return statement should be return string[i];

-
repeater is a terrible name if you are planning to return a non-repeater ;)

-
from a design perspective, I would return '' instead of 'Everything is repeated', because really, '' aka nothing is repeating

On the whole I think your code is fine, I am not sure ( besides the magical regex ) how it could be done much faster. You need something to track the character count and I am not sure how you can avoid the second loop.

Update: books.google.com/books?isbn=1118169387 <- This pretty much agrees that your first approach is as fast as it gets ( except for the mind boggling regex ;)

StackExchange Code Review Q#45228, answer score: 8