Longest Substring without Repeating Characters

Question

Given a string, find the length of the longest substring without repeating characters.

Example For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3.

For "bbbbb" the longest substring is "b", with the length of 1.

Challenge O(n) time

Thoughts

two pointers的题目, 同向型 如果发现了一个符合条件的sub-array [i, j], 即可知道[i,i+1], [i,i+2]....等都符合条件，并且小于[i, j]的value,所以可以不用再计算，所以在每个Loop里j不用再重设回i。

j一直尽可能地往前拓展，如果到了不能满足条件的地方，就将i位置的char去掉，直到能够重新满足条件

Solution

class Solution:
    # @param s: a string
    # @return: an integer
    def lengthOfLongestSubstring(self, s):
        # write your code here
        map = {}
        i = 0
        j = 0
        ans = 0

        for i in range(len(s)):
            while j < len(s) and (s[j] not in map or map[s[j]] == False) :
                map[s[j]] = True
                ans = max(ans, j - i + 1)
                j += 1
            map[s[i]] = False

        return ans