first_non_repeating.py

# Given an input string, it gives the
# first non repeating character in it
# There are two implementations below
# 1. has less space complexity
# 2. has less time complexity


deffirst_non_repeating(input_string):
frequency=dict()
flag=None

forcharininput_string:
ifcharinfrequency.keys():
frequency[char] +=1
else:
frequency[char] =0

forcharininput_string:
iffrequency[char] ==0:
flag=char
break

returnflag


# lesser time complexity
# more space complexity
# obvious space-time trade-off
deffirst_non_repeating_v2(input_string):

flag=None
repeating= []
non_repeating= []

forcharininput_string:
ifcharinnon_repeating:
non_repeating.remove(char)
repeating.append(char)
else:
non_repeating.append(char)

iflen(non_repeating) ==0:
pass
else:
flag=non_repeating[0]

returnflag


result=first_non_repeating("djebdedbekfrnkfnduwbdwkd")
print(result) # j

result=first_non_repeating("aabbcc")
print(result) # None