Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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.

share|improve this question
    
first solution is O(n) so as good as it gets, but instead of 'More than one' and 'One Time' I would change the values to a boolean or int, checking if charCount[string[j]] === 'One Time' on each index is probable slower than multiple[string[j]] === true –  Rodolfo Mar 24 at 18:16
    
Interesting: in a higher-level language (R example here), this would be (rle is "run-length encoder" ) foo<- rle(sort(my.data)); bar<- foo$values[foo$lengths==1][1]; which(my.data==bar) –  Carl Witthoft Mar 24 at 19:07
    
You probably should use hasOwnProperty to check for the presence on a key in the set. –  CodesInChaos Mar 25 at 11:48
    
Is the search case sensitive? i.e., does "taTer" still match t as the first non-repeater, or would it be a? –  samanime Mar 25 at 21:51

7 Answers 7

up vote 8 down vote accepted

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 ;)

share|improve this answer

The runtime of the 1st solution you posted is not O(n2). You are just traversing the string twice, which makes it O(2n) => O(n).

share|improve this answer
1  
This doesn't look like a solution - it's more a comment –  Antonio Mar 24 at 15:54
3  
@Antonio I'd consider this an allowable answer under the "your code seems fine" rule. –  200_success Mar 24 at 16:10
2  
@200_success I thought the reviewer then ought to state why the code is fine ? meta.codereview.stackexchange.com/questions/850/… –  konijn Mar 24 at 16:13
1  
@ComFreek - the first solution is O(n) . If you double the length of the string, it takes twice as long, not 4 times as long. The performance is proportional to the length of the string. –  rolfl Mar 24 at 22:55
6  
@ComFreek - I understand you now. You are right, of course... just like it would be accurate to say the upper-bound of the speed Hussein Bolt runs is the speed of light. Accurate, but useless. –  rolfl Mar 25 at 13:44

I'm proposing a solution that in some cases can be better than your first algorithm, but not always - it mostly depends on the input string. I think that on average they have similar performance.

The idea is to use a regex to search and replace with an empty string all occurrences of the first character. If the resulting string has length equal to the length at the previous iteration minus 1, then that character is not repeated. The search is case insensitive

The advantage of this code is that it's more compact and readable, plus it immediately breaks as soon as a non repeating character is found.

var repeater = function(string) {
    var result = false;

    while (string) {
        var len = string.length;
        var char = string[0];
        var regex = new RegExp(char, "gi");
        string = string.replace(regex, "");
        if (string.length == len - 1) {
            result = char;
            break;
        }
    }
    return result;
}

Update: I ran a few benchmarks, and on average it takes less than your first algorithm (using code runner and node.js). This is the benchmarking code:

var start = Date.now();

for (var count = 0; count < 10000; ++count) {
    repeater('toTal');
    repeater('teEter');
    repeater('erttreert');
    repeater('repeaterqetyhgerdfcvvgfnk');
}

var end = Date.now();

console.log("\nTime: " + (end - start) + "ms");

and the results are around 60ms for my algorithm, 110-120ms for yours.

share|improve this answer
    
jsperf.com/first-non-repeated I dont think so, it would not make sense, the regex is O(n), so unless the first non-repeater is the first or the second character, your code should be slower. –  konijn Mar 24 at 17:31
    
Hmm... tested that, but it tells me repeater2 is better. repeater1 is reported as 56% slower. I'm on mac, using chrome. Are you using a different browser? –  Antonio Mar 24 at 17:38
    
Also tried with Safari, FF and IE, same outcome (but ofc with different numbers) –  Antonio Mar 24 at 17:41
    
Chrome, windows ( Chrome 35.0.1897 (1)), which is funny, the only combo where the OP code is faster, most interesting. –  konijn Mar 24 at 17:43
1  
I think it would be more fair if the OP used 1 and 2 instead of "More than One" and "One Time" –  Cruncher Mar 24 at 20:43

This solution has an upper bound of O(n^2) and an lower bound of O(n). It has a good average performance for short strings and strings with many repeated characters.

function repeater(string)
{
  if(string.length==0)
    return false;

  var char = string.charAt(0);
  if(string.lastIndexOf(char) == 0)
    return char;

  for(var i = 1; i < string.length-1; ++i)
  {
    char = string.charAt(i);
    if(string.lastIndexOf(char)==i && string.indexOf(char)==i)
      return char;
  }

  char = string.charAt(string.length-1);
  if(string.indexOf(char)==string.length-1)
    return char;

  return false;
}

Edit

I found a faster solution. This solution has an upper bound of O(n^2-n/2) and a lower bound of O(n). It is about 25 times faster than the original and 3 times faster than my previous version. See jsperf.

var g_string = new Uint32Array(100);
function repeater(string)
{
  if(string.length==0)
    return false;
  if(string.length>g_string.length)
    g_string = new Uint32Array(string.length);

  var length = 0;
  var char = string.charCodeAt(0);
  for(var i=1;i<string.length;++i)
  {
    var chari = string.charCodeAt(i);
    if(chari != char)
      g_string[length++] = chari;
  }
  if(length == string.length-1)
    return String.fromCharCode(char);

  while(length)
  {
    var char = g_string[0];
    var length_new = 0;
    for(var i=1;i<length;++i)
    {
      if(g_string[i] != char)
        g_string[length_new++] = g_string[i];
    }
    if(length_new == length-1)
      return String.fromCharCode(char);
    length = length_new;
  }

  return false;
}

This function removes the first character from the string and copies in-place all characters that don't match the first character into an array. This is repeated until no duplicates are found for a character or the array is empty. What makes this version so fast is that the array is allocated in the global namespace. It only needs to be reallocated when you pass a string longer than the array.

Edit 2

Okay last one I swear. This version is only about 10% faster than the previous solution, but I think it is notable because it is O(n) in every case. Note that this one will not work for character codes > 255, which makes it bad for most real world applications.

var g_string = new Uint32Array(100);
var g_char = new Uint32Array(256);
function repeater(string)
{
  if(string.length>g_string.length)
    g_string = new Uint32Array(string.length);
  for(var i=0;i<string.length;++i)
  {
    g_string[i]=string.charCodeAt(i)&0xFF;
    ++g_char[g_string[i]];
  }
  var ret = false;
  for(var i=0;i<string.length;++i)
  {
    if(g_char[g_string[i]]==1)
    {
      ret = string[i];
      break;
    }
  }
  for(var i=0;i<string.length;++i)
    g_char[g_string[i]] = 0;
  return ret;
}

It increments a character frequency table for each character in the string. Then it iterates over the string again until it finds a character with a frequency of 1. It iterates over the string one final time and zeros the character frequency table so that we can reuse it.

share|improve this answer

This is an interesting problem. I added one which seems to perform a bit better (though it might just be on Chrome + Windows, it performs just a hair better than repeater2).

It is O(n).

function repeater4(test) {
    while (test && /^(.)(?:.*\1)/.test(test)) {
        test = test.replace(new RegExp(test[0], 'g'), '');
    }

    return test ? ('Matched: ' + test[0]) : 'No matches';
}

JSPerf: http://jsperf.com/first-non-repeated/3

I feel like there is an O(1) solution to this using regex though. I'm mucking around to see if I can come up with something.

Edit

Upon thinking, I realized that regex is O(n) (at best), so really there isn't an O(1) method that is possible. Interesting problem, and there is probably some really clever way of speeding it up even more, but I think the solution I came up with seems to be both relatively quick and elegant, so I'll leave it at that.

share|improve this answer
    
This function function assumes the input will only contain letters and it does a case insensitive match. You can change the regex to /^(.)(?:.*\1)/ to make it behave more like the original and a tiny bit faster. Also, I don't think the fastest solution is a RegExp see the updated jsperf. jsperf.com/first-non-repeated/5 –  Bob65536 Mar 25 at 22:47
    
I wasn't sure if it was supposed to be case sensitive or insensitive, so I opted for insensitive, though obviously it is a simple change either way. Also, good catch. When I first read it I was thinking letter, but that's a requirement I just made up in my head. I'll update my code example. Thanks. –  samanime Mar 25 at 22:52
    
@Bob65536 Nice solution using lastIndex. That is substantially faster. –  samanime Mar 25 at 22:54
    
Thanks. Removing duplicates as they are found would make subsequent searches faster, but unfortunately strings in javascript are immutable. I found that creating a new string or converting the string to an array is too much overhead for small inputs. I like your idea of using a regex to check if the first character is unique. –  Bob65536 Mar 25 at 23:06

This is actually a pretty interesting question, and it shows that big O notation can be misleading.

Your first attempt is pretty good. It does loop through the string twice, so you might think that it's O(n), but each iteration is doing a lookup on the charCount dictionary. Now charCount can have at most i entries each time through, how does that effect our complexity? It's hard to say; the JS engine can implement this in several ways, but it's probably not constant time. Lookups like this tend to be O(log n) so I'd say overall your first implementation is O(n log n) (worst case).

The regular expression solution that seems to be fastest (in clock time) is far less "efficient". We know that applying regular expressions is O(n) and doing it in a loop will end up being O(n2) worst case. But the regex engine is written in C and is a core part of the js engine, so it's very believable that applying a regex can be much faster than looping through a string in JavaScript. So from an algorithmic standpoint, it's O(n2), but you would not expect the performance graph to look anything like a parabola.

share|improve this answer

My 2c, not nearly as fast as regex unfortunately:

function firstNonRepeatedChar(str) {
  chars = {};
  for(var i=0; i<str.length; i++) {
    var c = str[i];
    chars.hasOwnProperty(c) ? chars[c]++ : chars[c] = 0;
  }

  var result;
  for(var key in chars) {
    if(chars[key] == 0) {
      return key;
    }
  }    
}
share|improve this answer
    
This is not guaranteed to return the first occurence –  konijn Mar 25 at 0:36
    
How come? Don't keys stay on object in order they were added on? –  Matjaz Muhic Mar 25 at 6:56
    
developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/… -> A for...in loop iterates over the properties of an object in an arbitrary order –  konijn Mar 25 at 12:30
    
Ah the loop... :/ –  Matjaz Muhic Mar 25 at 14:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.