请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例1：

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

提示：

• s.length <= 40000

class Solution:
	def lengthOfLongestSubstring(self, s):

解题思路：

长度为$N$的字符串共有$\frac{(1+N)N}{2}$个子字符串(复杂度为$O(N^2)$)，判断长度为$N$的字符串是否有重复字符的复杂度为$O(N)$，因此本题使用暴力法解决的复杂度为$O(N^3)$。

考虑使用动态规划降低时间复杂度。

动态规划解析：

• 状态定义：设动态规划列表$dp$，$dp[j]$代表以字符$s[j]$为结尾的”最长不重复子字符串”的长度。
• 转移方程：固定右边界$j$，设字符$s[j]$左边距离最近的相同字符为$s[i]$，即$s[i]=s[j]$。

1. 当$i<0$，即$s[j]$左边无相同字符，则$dp[j] = dp[j-1]+1$;
2. 当$dp[j-1]<j-i$，说明字符$s[i]$在子字符串$dp[j-1]$区间之外，则$dp[j]$的左边界由$s[i]$决定，即$dp[j] = j-i$;
3. 当$dp[j-1]>=j-i$，说明字符$s[i]$在子字符串$dp[j-1]$区间之中，则$dp[j]$的左边界由$s[i]$决定，即$dp[j]=j-i$。

当$i<0$时，由于$dp[j-1]<=j$恒成立，因此$dp[j-1]<j-i$恒成立，因此分支1和2可被合并。

返回值：$max(dp)$，即全局的”最长不重复子字符串”的长度。

方法一：动态规划+哈希表

• 哈希表统计：遍历字符串$s$时，使用哈希表(记为dic)统计各字符最后一次出现的索引位置。
• 左边界$i$获取方式：遍历至$s[j]$时，可通过访问哈希表dic[s[j]]获取相近的相同字符的索引$i$。

复杂度分析：

• 时间复杂度$O(N)$：其中$N$为字符串长度，动态规划需遍历计算$dp$列表。
• 空间复杂度$O(1)$：字符的ASCII码范围为0~127，哈希表dic最多使用$O(128)=O(1)$大小的额外空间。

python的get(key, default)方法代表当哈希表包含键key时返回对应value，不包含时返回默认值default。

class Solution:
	def lengthOfLongestSubstring(self, s):
        dic = {}
        res = tmp = 0
        for j in range(len(s)):
            i = dic.get(s[j],-1) # 获取索引i
            dic[s[j]] = j # 更新哈希表
            tmp = tmp + 1 if tmp < j - i else j - i
            res = max(res, tmp)
        return res

方法二：动态规划+线性遍历

• 左边界$i$获取方式：遍历到$s[j]$时，初始化索引$i = j - 1$，向左遍历搜索第一个满足$s[i]=s[j]$的字符即可。

复杂度分析：

• 时间复杂度$O(N^2)$:
• 空间复杂度$O(1)$

方法三：双指针+哈希表

与方法一本质等价，不同点在于左边界的定义不同。

• 哈希表dic统计：指针$j$遍历字符$s$，哈希表统计字符$s[j]$最后一次出现的索引。
• 更新左指针$i$：根据上轮左指针$i$和$dic[s[j]]$，每轮更新左边界$i$，保证区间$[i+1, j]$内无重复字符且最大。
• 更新结果$res$：取上轮$res$和本轮双指针区间$[i+1, j]$的宽度(即$j-i$)

class Solution:
	def lengthOfLongestSubString(self, s):
		dic, res, i = {}, 0, -1
		for j in range(len(s)):
			if s[j] in dic:
				i = max(dic[s[j]], i) # 更新左指针i
			dic[s[j]] = j # 哈希表记录
			res = max(res, j-i) # 更新结果
		return res