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

解题思路：使用哈希表记录每个字符最后一次出现的位置，遍历字符串时判断当前字符是否已经出现过，若出现过，则更新不重复子串的起始位置，否则更新最长长度和当前字符的位置。

Python代码实现：

def length_of_longest_substring(s):
    if not s:
        return 0
    char_index = {}
    start = 0
    max_len = 0
    for i in range(len(s)):
        if s[i] in char_index and char_index[s[i]] >= start:
            start = char_index[s[i]] + 1
        else:
            max_len = max(max_len, i - start + 1)
        char_index[s[i]] = i
    return max_len

时间复杂度：O(n)。

相关问题

最长不重复子串问题：给定一个字符串S，返回S中所有字符的最长不重复子串的长度。如果S为空，返回0。

算法思路：

使用双指针left和right维护一个滑动窗口，表示当前不重复子串的范围。初始时，left和right都指向字符串的第一个字符。

在移动right指针的过程中，维护一个哈希表或数组，记录每个字符最后一次出现的位置。假设当前right指针指向的字符是s，如果s已经在哈希表中存在（即s在[left,right)范围内），则将[left,right)区间中所有s之前的字符都从哈希表中删除，同时将left指针移到s上一次出现位置的下一个位置，即left=hash[s]+1。

同时，每次移动right指针时，都需要更新该字符最后一次出现的位置hash[s]=right。

在移动right指针的过程中，使用一个变量maxlen记录最长不重复子串的长度。

算法实现：

时间复杂度为O(n)，空间复杂度为O(n)。

Python代码实现：

Python代码实现：最长不重复子串问题：给定一个字符串S，返回S中所有字符的最长不重复子串的长度。如果S为空，返回0。

示例：

输入： "abcabcbb"
输出： 3
解释： 最长的不重复子串是 "abc"，其长度为3。

输入： "bbbb"
输出： 1
解释： 最长的不重复子串是 "b"，其长度为1。

输入： ""
输出： 0

代码实现：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        
        left = res = 0
        lookup = set()
        for right in range(len(s)):
            while s[right] in lookup:
                lookup.remove(s[left])
                left += 1
            lookup.add(s[right])
            res = max(res, right - left + 1)
            
        return res

解析：

使用一个滑动窗口来维护最长的不重复子串。初始时，窗口左右端点都指向字符串的起始位置。然后逐个向右移动右端点，并将右端点指向的字符加入到集合中。

如果当前字符已经在集合中存在，说明窗口中已经存在重复字符，那么就需要从窗口左端点开始移动，并将左端点指向的字符从集合中删除，直到窗口中不再有重复的字符。

在移动窗口的过程中，我们需要不断地记录最长的不重复子串的长度，并更新结果res。

时间复杂度：O(n)
空间复杂度：O(n)