Python, Exactly one-pass, No built-in function, Accepted Solution


  • 0
    A
    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

  • 0
    A

    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

  • 0
    A

    @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)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.