題目

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

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

難度

Medium

方法

采用滑動窗口的方法驾凶，left指窗口左邊界调违，right指窗口右邊界技肩，positions用來記錄每個字符對應的位置浮声。先固定left，將right向右移動然痊，如果positions[s[right]]不存在屉符，則表示從left到right中沒有出現(xiàn)相同字符矗钟，此時計算下長度，跟最大長度比較下看是否更新最大長度吨艇；如果positions[s[right]]已存在东涡，并且>=left，則說明s[right]這個字符已經(jīng)在[left, right]這個區(qū)間里出現(xiàn)過1次了桑谍，則需要移動left锣披，直到position[s[right] < left為止

python代碼

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :param s: str
        :return: int
        """
        positions = {}
        longest_length = 0
        right = 0
        for left in range(len(s)):
            # right = left is redudant
            while right < len(s):
                position = positions.get(s[right])
                if position is not None and position >= left:
                    break
                else:
                    positions[s[right]] = right
                    longest_length = max(longest_length, right - left + 1)
                right += 1

        return longest_length


assert Solution().lengthOfLongestSubstring("abcabcbb") == 3
assert Solution().lengthOfLongestSubstring("bbbbb") == 1
assert Solution().lengthOfLongestSubstring("abcdaefg") == 7
assert Solution().lengthOfLongestSubstring("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789\
    !\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789\
    !\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789\
    !\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789\
    !\"#$%&'()*+,-./:;<=>?@[\\]^_`{|}~ abcdefghijklmnopqrstuvwxyzABCD") == 95