Complexity Analysis
def first_unique(s):
freq = {}
for c in s:
freq[c] = freq.get(c, 0) + 1
for c in s:
if freq[c] == 1:
return c
return NoneWhat is the time and space complexity?
Work it out before scrolling down.
Time
O(n)
Space
O(1)
How to derive it
Two passes through the string, each O(n). The freq dict stores at most 26 entries (assuming lowercase English letters) — this is O(1), not O(n), because the alphabet size is a constant. If the character set were unbounded, space would be O(k) where k is the number of distinct characters.