[LeetCode]3. Longest Substring W

题目

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中没有出现相同字符，此时计算下长度，跟最大长度比较下看是否更新最大长度；如果positions[s[right]]已存在，并且>=left，则说明s[right]这个字符已经在[left, right]这个区间里出现过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