Best way to find first non repeating character in a string
algorithm, python
Solution
Here's a very straightforward `O(n)` solution:
def fn(s):
order = []
counts = {}
for x in s:
if x in counts:
counts[x] += 1
else:
counts[x] = 1
order.append(x)
for x in order:
if counts[x] == 1:
return x
return None
We loop through the string once. When we come across a new character, we store it in `counts` with a value of `1`, and append it to `order`. When we come across a character we've seen before, we increment its value in `counts`. Finally, we loop through `order` until we find a character with a value of `1` in `counts` and return it.
Problem
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).