Easy to understand Python solution

  • 0

    I used a hashmap and a queue to implement this. Here is the logic,

    1. For every element update it's index in the map. Also enqueue this.
    2. If the element is already in the map then dequeue elements (index - startIndex) times. Set the startIndex to index+1
    3. Compare length of the queue with the maxLength
        def lengthOfLongestSubstring(self, s):
             maxLength = 0
            smallestIndex,fromIndex,queue = {},0,[]
            for i in range(len(s)):
                if s[i] in smallestIndex:
                    while fromIndex<=smallestIndex[s[i]]:
                        del queue[0]
                        fromIndex = fromIndex + 1
                smallestIndex[s[i]] = i
                maxLength = max(maxLength,len(queue))
            return maxLength

    A more efficient approach would be to git rid of the queue entirely but this solution is easier to understand.

Log in to reply

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