I am solving a problem: Given a string s consisting of small English letters, find and return the first instance of a non-repeating character in it. If there is no such character, return ‘_’.
For example: s = “abacabad”, the output should be firstNotRepeatingCharacter(s) = ‘c’.
I wrote a simple code, it got through all the test, but when I submit it, it reports error, anyone know what’s wrong with my code? Thank you!
def firstNotRepeatingCharacter(s): for i in list(s): if list(s).count(i) == 1: return i return '_'
Advertisement
Answer
Could be a performance issue as your repeated count
(and unnecessary list conversions) calls make this approach quadratic. You should aim for a linear solution:
from collections import Counter def firstNotRepeatingCharacter(s): c = Counter(s) for i in s: if c[i] == 1: return i return '_'
You can also use next
with a generator and a default value:
def firstNotRepeatingCharacter(s): c = Counter(s) return next((i for i in s if c[i] == 1), '_')
If you can only use built-ins, just make your own counter (or any other data structure that allows you to identify duplicates)
def firstNotRepeatingCharacter(s): c = {} for i in s: c[i] = c.get(i, 0) + 1 return next((i for i in s if c[i] == 1), '_')