题目

给定一个字符串 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;