Best way to find first non repeating character in a string

What would be the best space and time efficient solution to find the first non repeating character for a string like aabccbdcbe?

The answer here is d. So the point that strikes me is that it can be done in two ways:

For every index i loop i-1 times and check if that character occurs ever again. But this is not efficient: growth of this method is O(N^2) where N is the length of the string.
Another possible good way could be if I could form a tree or any other ds such that I could order the character based on the weights (the occurrence count). This could take me just one loop of length N through the string to form the structure. That is just O(N) + O(time to build tree or any ds).

python algorithm

Edit Report

-1

So from the definition of the problem, it's clear that you need an O(n) solution, which means only going through the list once. All of the solutions which use a form of count are wrong, since they go through the list again in that operation. So you need to keep track of the counts yourself.

If you only had characters in that string, then you don't need to worry about storage and you could just use the character as a key in a dict. The values in that dict will be the index of the character in the string s. At the end we have to see which one was the first by calculating the minimum of the dictionary's values. This is an O(n) operation on a (possibly) shorter list than the first.

The total will still be O(c*n) therefore O(n).

from operator import itemgetter

seen = set()
only_appear_once = dict()

for i, x in enumerate(s):
  if x in seen and x in only_appear_once:
    only_appear_once.pop(x)
  else:
    seen.add(x)
    only_appear_once[x] = i

first_count_of_one = only_appear_once[min(only_appear_once.values(), key=itemgetter(1))]

answered 2013-03-19T09:56:18.137

Best way to find first non repeating character in a string

1 Answer

Your Answer