LeetCode.3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

根据官方题解的思路：
利用Set构建滑动窗口。

滑动窗口是指 数组/字符串 由开始和结束索引构建的一系列字符的集合。

• 例如窗口：[i,j)(左闭，右开)。从索引i开始到索引j结束（不含j）的所有元素的集合。
• 窗口的两个边界可以向某一个方向滑动。例如两个边界都向右移，滑动窗口就是[i+1,j+1)。

利用set构建滑动窗口，

• 最初[i,j),i = j。字符串为s。
• 滑动右边界，即j自增1，如果是s[j],不在集合中，那么j继续向右移动一位。所以找到的最长无重复索引子串都是以i开头的。对所有的i都这样操作。就可以得到答案。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        i,j,ans = 0,0,0  #初始化滑动窗口，和子串的长度。
        charset = set()
        while i<n and j <n:
            if s[j] not in charset:  #如果s[j]不在集合中，集合就添加s[j],然后j自增1
          
                charset.add(s[j])
                j += 1
                ans = max(ans,j-i)  # 如果集合中大于最长无重复子串的长度，就更新ans
            else:               
                charset.remove(s[i]) #如果s[j]在集合中，滑动窗口的左边界向右移动一位。所以set就应该移除这一个s[i]。继续滑动右边界。
                i += 1
        return ans

优化的滑动窗口

上一个算法，是逐步增大i。
即对于字符串如果滑动窗口滑动到[i,j)，s[j]与滑动窗口中的一个字符重复。然后将i自增1.
更加优化的算法是。利用一个hash表存储字符在字符串上一次出现的位置。如果滑动窗口滑动到[i,j)，s[j]与滑动窗口中的一个字符重复。查找hash表的元素s[j],就可以查到字符s[j]在滑动窗口出现位置的索引$j^{'}$j′。然后让$i = j^{'}+1$i=j′+1。继续滑动右边界。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        i,ans = 0,0
        charmap = {}
        for j in range(n):
            if s[j] in charmap:
                i = max(charmap[s[j]],i)  # 如果s[j]在set中，i = j' + 1
            ans = max(ans,j-i+1)
            charmap[s[j]] = j+1
        return ans