def firstUniqChar(self, s):
"""
:type s: str
:rtype: int
"""
map = [0]*26
i,j = 0,0
n = len(s)
while(j<n and i<n):
if i==j or s[i] != s[j] :
map[ord(s[j])ord('a')] += 1
j+=1
else:
map[ord(s[j])ord('a')] += 1
while(i<n and (map[ord(s[i])ord('a')]>1) ):
i += 1
if i>=n :
return 1
else:
return i
Python, Exactly onepass, No builtin function, Accepted Solution


Valid solution.... But the complexity is O(n^2) , since you have 2 while loops... Not optimal...
You can do in 2 passes.... Much better than yours... The trick is to do that in single pass, without increasing space complexity.. Can you do that ?
a = [0] * 26 for i in s: a[ord(i)ord('a')]+=1 for i in s: if a[ord(i) ord('a')] == 1: return s.index(i) return 1

@anilbpai I think this is one pass, there are two while loops, but you need to follow i and j.
if you trace it by hand, you see that it is O(n)