How to maximize python efficiency?

Question

I am working on a Code Signal practice interview question and my code passes 16/19 tests but the ones it is failing the rest due to exceeding the allowed time limit.

I tried using set() instead of a list but then the count method doesn't work, and since I'm extremely new to python I don't know a better alternative.

def firstNotRepeatingCharacter(s):
 list = []
 num = '_'
 for i in s:
 list.append(i)
 for i in list:
 if list.count(i) <= 1:
 num = i
 return num
 return num

• Nir Alfasi: Use a Set. Before you add a character check if it's not already there. The improvements that you'll get are: 1. search time in a Set is O(1) instead of O(n) in a list. 2. You don't have to iterate the list twice.
• Tomerikoo: why do you copy the string to a list? why not just for i in s: if s.count(i) == 1: num = i
• Jerry Jeremiah: @Tomerikoo I don't know Python but does everything that can be enumerated with a loop include a count member?
• Tomerikoo: @alfasin how would you then know which was the first character as sets don't have order?
• Kaz: @alfasin "Before you add a character, check if it's not already there". So then, what will the resulting set inform you about? It will contain all of the characters from the string after processing the string. If you use two sets, you can do this: the first time a character is seen it goes to the seen set. If a character is already in the seen set, it goes to seen_again set. The first non-repeating character is then the leftmost one which does not appear in the seen_again set. Or else a histogram dictionary could be used.

Answer 1

If you're using Python 3.7+, where dict keys are insertion-ordered, you can use collections.Counter:

from collections import Counter
def firstNotRepeatingCharacter(s):
 return next((char for char, count in Counter(s).items() if count == 1), '_')

With prior versions of Python, you can use collections.OrderedDict to keep track of the counts instead:

from collections import OrderedDict
def firstNotRepeatingCharacter(s):
 counts = OrderedDict()
 for char in s:
 counts[char] = counts.get(char, 0) + 1
 return next((char for char, count in counts.items() if count == 1), '_')

so that firstNotRepeatingCharacter('aababdcbcea') returns: 'd'

Both of the above code snippets have a time complexity of O(n), as opposed to O(n ^ 2) in your solution due to your use of the list.count method in a loop.

• Tomerikoo: upvoted. To make this a truly remarkable answer, edit in some links. Here they are ;) counter, orederedDict

Answer 2

You can have a dictionary to mantain counter of each character and check which char count is 1. This computes in O(N), your solution takes O(N^2) due to list.count() method

def firstNotRepeatingCharacter(s):
 num = '-'
 d = {}
 for i in s:
 d[i] = d.get(i, 0) + 1
 for i in s:
 if d[i] == 1:
 return i
 return num