3 ms·
Here's my Python implementation. It scans the string only once. It allocates at most 2*len(alphabet) characters while scanning the string. It also bails early i
by cpeterso 15y ago
Here's my Python implementation. It scans the string only once. It allocates at most 2*len(alphabet) characters while scanning the string. It also bails early if every character in the alphabet has been repeated.
import string
def first_nonrepeating_char(s, alphabet=string.printable):
notrepeated = [] # remember order of appearance!
repeated = [] # set of repeated chars, order unimportant
for c in s:
if c in notrepeated:
# c has now been repeated!
notrepeated.remove(c)
repeated.append(c)
if len(repeated) == len(alphabet):
return None # every letter repeated!
elif c not in repeated:
# we have not seen c before
notrepeated.append(c)
return notrepeated[0] if len(notrepeated) > 0 else None
assert first_nonrepeating_char('trait') == 'r'
assert first_nonrepeating_char('aardvark') == 'd'
assert first_nonrepeating_char('aabbac') == 'c'
assert first_nonrepeating_char('aabacc') == 'b'
assert first_nonrepeating_char('aaba ccdbe') == ' '
assert first_nonrepeating_char('aabad ccbe') == 'd'
- kenjackson 15y agoLooks good. Although is [] associative in Python (haven't coded in Python in about 12 years)? The append method makes me think it isn't. If it's not then it goes from: O(n) where n is the length of the string to O(mn) where m is the length of the alphabet -- although m is small, so maybe not that bad of a deal, you could almost treat it is a constant factor, since it will be dwarfed by n. I do like the early exit.
- cpeterso 15y agoGood point. Python's [] is a list (array). I considered using a Python dictionary, but that seemed wasteful for a small alphabet. Python does have a built-in set() class, which would have been more appropriate.