题目

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

输出: s = "abcabcbb"
输入: 3 
解释: 因为无反复字符的最长子串是 "abc"，所以其长度为 3。输出: s = "bbbbb"
输入: 1
解释: 因为无反复字符的最长子串是 "b"，所以其长度为 1。输出: s = "pwwkew"
输入: 3
解释: 因为无反复字符的最长子串是 "wke"，所以其长度为 3。请留神，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

暴力枚举

思路一：以每个字符为开始，遍历字符串，用一个字典保留遍历的字符，遇到反复的就完结，用一个数组保留本次无反复子串的长度，返回最大的

def lengthOfLongestSubstring(s):
    if not s:
        return 0
    
    slen = [1] * len(s)
    for i in range(0,len(s)):
        hashTable = {}
        hashTable[s[i]]=1
        for j in range(i+1, len(s)):
            if s[j] in hashTable:
                break
            else:
                hashTable[s[j]]=1
                slen[i]+=1
    return max(slen)

滑动窗口

# 思路二：滑动窗口
# 定义两个指针，i 和 j，i 作为无反复子串的结尾，j 作为无反复子串的结尾
# 定义一个字典 st，用来保留每个字符的最初一次呈现的地位
# 定义一个 ans 变量，用来保留最长无反复子串的长度
# 初始时，i,j=0，都在结尾地位
# 随着 for 循环遍历字符，j 一直向后挪动
# 在 j 挪动的过程中，如果以后字符在 st 中曾经存在了，阐明之前的字符中存在雷同的字符，这段无反复子串到此就完结了，须要挪动 i 来调整窗口
# 挪动 i 时须要留神：# 在挪动前，如果 i 的地位 <= 反复字符的最新地位（..[i.. 反复字符..j]..)，# 阐明反复字符就在以后窗口中，须要将 i 挪动到反复字符的下一个地位(.. 反复字符[i..j]..)
# 如果 i 的地位 > 反复字符的最新地位 (.. 反复字符..[i..j]..)，# 阐明反复字符在以后窗口后面，并不在以后窗口中，以后窗口的子串是无反复的，则 i 放弃不动，# i 和 j 的地位都确定好后，再更新 ans，ans=Max(ans, j-i+1)，以后的长度和之前的长度比拟，选最大的，让 ans 保留的是最大长度
# 最初将 {以后字符: 呈现的位值} 保留在字典 st 中

def lengthOfLongestSubstring(s):
    st = {}
    i, ans = 0, 0
    for j in range(len(s)):
        if s[j] in st:
            i = max(i, st[s[j]]+1)
        ans = max(ans,j-i+1)
        st[s[j]] = j
    return ans;