9.最长不重复子串问题：给定一个字符串S，返回S中所有字符的最长不重复子串的长度。如果S为空，返回0。 例如： 输入：S = “abcabcbb” 输出：3 解释：最长不重复子串是"abc"，长度为3。 输入：S = “bbbbb” 输出：1 解释：最长不重复子串是"b"，长度为1

解法一：滑动窗口

算法思路：

使用 left 指针表示当前不重复子串的左边界，right 指针向右遍历字符串，使用 set 存储当前子串中出现过的字符，当 right 指向的字符已经在 set 中出现过时，将 left 指针右移，直到将重复的字符从 set 中移除，重新计算当前子串的长度并更新最长子串长度。

算法流程：

初始化 left、right、max_len 和 set
当 right 小于 n（字符串长度）时：
如果当前字符 ch 不在 set 中：
将当前字符 ch 添加到 set 中
更新 max_len 为 max(max_len, right - left + 1)
将 right 右移
如果当前字符 ch 在 set 中：
从 set 中移除 left 对应的字符
将 left 右移
返回 max_len

时间复杂度：遍历一遍字符串，时间复杂度为 O(n)。

空间复杂度：使用了 set 存储字符，最坏情况下字符串中每个字符都不相同，空间复杂度为 O(n)。

Python3 代码实现：

class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n = len(s)
left, right = 0, 0
max_len = 0
char_set = set()
while right < n:
if s[right] not in char_set:
char_set.add(s[right])
max_len = max(max_len, right - left + 1)
right += 1
else:
char_set.remove(s[left])
left += 1
return max_len if s else 0

解法二：动态规划

算法思路：

使用 dp[i] 表示以第 i 个字符结尾的最长不重复子串的长度，使用 dict 存储当前字符上一次出现的位置，如果当前字符上一次出现的位置在当前不重复子串的左边界左边，说明当前字符没有出现过，可以更新 dp[i]，否则当前字符已经出现过，左边界需要向右移动，同时也需要更新 dp[i]。

算法流程：

初始化 dp 和 dict
当 i 小于 n（字符串长度）时：
如果当前字符 s[i] 没有在 dict 中出现过或者出现位置在左边界 i - dp[i-1] 左边：
dp[i] = dp[i-1] + 1
否则：
dp[i] = i - dict[s[i]]
更新 dict 中 s[i] 的出现位置
如果 dp[i] 大于 max_len，将 max_len 更新为 dp[i]
返回 max_len

时间复杂度：遍历一遍字符串，时间复杂度为 O(n)。

空间复杂度：使用了 dp 数组和 dict，空间复杂度为 O(n)。

Python3 代码实现：

class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
n = len(s)
if n == 0:
return 0
dp = [0] * n
dp[0] = 1
dict = {s[0]:0}
max_len = 1
for i in range(1, n):
if s[i] not in dict or i - dict[s[i]] > dp[i-1]:
dp[i] = dp[i-1] + 1
else:
dp[i] = i - dict[s[i]]
dict[s[i]] = i
max_len = max(max_len, dp[i])
return max_len