WillWang-X
7/15/2017 - 12:31 AM

3. Longest Substring Without Repeating Characters.py

# Time:  O(n)
# Space: O(1)
# 3. Longest substring without repeating characters


class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        longest, start, visited = 0, 0, [False for _ in range(256)] #ascii
        for i, char in enumerate(s):
            if visited[ord(char)]:   # abca  -b    what if abcac
                while char != s[start]: # a = Flase   
                    visited[ord(s[start])] = False
                    start += 1
                start += 1
            else:
                visited[ord(char)] = True
            
            longest = max(longest, i - start + 1)
        return longest