Python版本无重复字符的最长子串

题目描述：

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

示例 1：

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

示例 2：

输入: s = "bbbbb"
输出: 1
解释：最长的无重复字符的子串是 "b"，其长度为 1。

示例 3：

输入: s = "pwwkew"
输出: 3
解释：最长的无重复字符的子串是 "wke"，其长度为 3。

代码实现（Python）：

def lengthOfLongestSubstring(s):
    # 使用字典存储字符及其索引
    char_dict = {}
    # 初始化最长子串长度和滑动窗口的左右边界
    max_length = 0
    left = 0
    # 遍历字符串
    for right in range(len(s)):
        # 如果字符已经存在于字典中，并且索引大于等于左边界
        if s[right] in char_dict and char_dict[s[right]] >= left:
            # 更新左边界为重复字符的下一个索引
            left = char_dict[s[right]] + 1
        # 更新字符的索引
        char_dict[s[right]] = right
        # 更新最长子串长度
        max_length = max(max_length, right - left + 1)
    # 返回最长子串长度
    return max_length

# 测试代码
s1 = "abcabcbb"
s2 = "bbbbb"
s3 = "pwwkew"
print(lengthOfLongestSubstring(s1))  # 输出: 3
print(lengthOfLongestSubstring(s2))  # 输出: 1
print(lengthOfLongestSubstring(s3))  # 输出: 3

代码讲解：

1. 滑动窗口：我们使用两个指针 left 和 right 来表示一个滑动窗口，这个窗口内的子串不包含重复字符。

2. 字典存储：使用一个字典 char_dict 来存储字符及其索引，键是字符，值是字符在字符串中的索引。

3. 遍历字符串：通过一个循环遍历字符串 s，right 指针向右移动。

4. 更新左边界：如果当前字符 s[right] 已经在字典中，并且其索引不小于左边界 left，则更新左边界 left 为重复字符的下一个索引。

5. 更新字符索引：无论字符是否重复，都更新字典中当前字符的索引为 right。

6. 更新最长子串长度：每次循环时，都计算当前窗口的长度 right - left + 1，并更新最长子串长度 max_length。

7. 返回结果：遍历结束后，返回最长子串的长度。

这个算法的时间复杂度是 O(n)，其中 n 是字符串的长度，因为我们只需要遍历一次字符串。空间复杂度是 O(min(n, m))，其中 m 是字符集的大小，最坏情况下，我们需要存储所有字符及其索引。在本题中，由于字符集大小是固定的（ASCII 字符集），空间复杂度可以认为是 O(1)。