转自Kindem的博客

问题

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.

最初的尝试

尝试了好几种做法：

1. 测试每一个可能构成的字符串内部是否有重复字符，记录内部无重复的字符串长度的最大值，判断字符串内部是否重复这一过程另外定义一个函数，函数内部使用set来运算
2. O(n^2)的双指针移动法

两种方法虽然都能获得正确的答案，但是问题在于，如果字符串过长，在Python语言的前提下，可能出现性能不足的问题，从而导致代码运行时间超过空间限制

巧妙的做法--滑动窗口法

相当于只运用了一个指针用来标记窗口右端，而窗口左端随着右端的更新而更新，十分精巧，主要思路：

1. 使用“滑动窗口”，由窗口左端left和窗口右端right构成，左右两端之中则是滑动窗口的内容，表示当前正在判断的字符串
2. 使用dict记录窗口中的字符在字符串中的位置
3. 只使用一重循环不断移动right，而left随着right的改变而改变，如果right下一个出现的字符不与窗口中的字符重复，则right右移一位，扩大窗口，如果right下一个出现的字符与窗口中的字符重复，则将left移动到窗口中重复字符的后一位
4. 在更新的过程中记录字符串的最大长度

Python3代码如下:

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s or len(s) == 0:
            return 0
        dic = {}
        left = 0
        max_length = 0
        for right in range(0, len(s)):
            left = max(left, dic[s[right]] + 1 if s[right] in dic.keys() else 0)
            max_length = max(max_length, right - left + 1)
            dic[s[right]] = right
        return max_length