3、无重复字符的最长子串

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

示例 1:

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

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

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:

输入: s = ""
输出: 0

第一种方法

自己没看答案前，自己想的一种方法。
受两数之和的启发，用一个字典用来存储那些无重复的字符。然后遍历输入的字符串，如果字典中没有，则存到字典，无重复子串长度+1；如果字典中有，则清空字典，看看后面有无重复子串。代码如下：

    if len(s) == 0:
        return 0

    # 用来记录无重复字符的最长子串的长度
    maxlength = 0
    # 用来记录无重复字符的子串的长度
    length = 0
    # 用来存储每个字符
    char_dict = {}

    for i, value in enumerate(s):
        # 字符还没字典中存在过，就以字符为Key存储在字典中
        # 并且无重复字符的子串长度 +1
        if value not in char_dict:
            char_dict[value] = i
            length += 1
        else:
            # 走到这里，是因为字符在字典中出现过了，也就是说出现重复字符了
            # 这时先比较maxlength和length的大小，更新记录之前最长的无重复字符子串的最长长度
            maxlength = max(maxlength, length)
            # 清空字典，重新存储字符，并看看后面还有没有无重复的字符子串
            char_dict.clear()
            char_dict[value] = i
            length = 1

    # 有可能最后无重复子串长度比前面的无重复子串的长度大
    # 所以返回两个中间的最大值
    return max(maxlength, length)

这种方法时间和空间复杂度最大都是O(n)，上面的几个示例能够通过，但是如果输入是“pwwkewa”，结果就不正常了，正确结果应该是4，但是输出是3。

第二种方法

经过对上面方法的改动，当输入是“pwwkewa”，结果也是4。但是这种方法的时间复杂度就有点高了，最复杂的情况应该是O(n!)。代码如下：

    if len(s) == 0:
        return 0

    # 用来记录无重复字符的最长子串的长度
    maxlength = 0
    # 用来记录无重复字符的子串的长度
    length = 0
    # 用来存储每个字符
    char_dict = {}
    # 用来记录遍历到第几个字符
    i = 0

    while i < len(s):
        value = s[i]
        # 字符还没字典中存在过，就以字符为Key存储在字典中
        # 并且无重复字符的子串长度 +1
        if value not in char_dict:
            char_dict[value] = i
            length += 1
        else:
            # 走到这里，是因为字符在字典中出现过了，也就是说出现重复字符了
            # 这时先比较maxlength和length的大小，更新记录之前最长的无重复字符子串的最长长度
            maxlength = max(maxlength, length)
            # 从出现重复子串的位置，重新遍历
            # 比如 pwksewa 当遍历到第二个w的时候，此时令i=1 ，下次从k开始算后面的无重复子串
            i = char_dict[value]
            # 清空字典，重新存储字符，并看看后面还有没有无重复的字符子串
            char_dict.clear()
            length = 0

        i += 1

    # 有可能最后无重复子串长度比前面的无重复子串的长度大
    # 所以返回两个中间的最大值
    return max(maxlength, length)

第三种方法

参考力扣官方答案，采用了滑动窗口的思想，其实和我上面的方法有点类似，只是官方相当于用了两个指针（即窗口的左右两边：i 和rk），右指针没有从第一个重复的位置开始算，是一直向右移的。更加优化，时间复杂度更低。代码如下：

# 哈希集合，记录每个字符是否出现过
    occ = set()
    n = len(s)
    # 右指针 rk，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
    # ans 记录 无重复字符子串的长度
    rk, ans = -1, 0
    for i in range(n):
        if i != 0:
            # 当i = 0时，集合中还没有字符，不需要移除
            # 左指针向右移动一格，移除左边一个字符
            occ.remove(s[i - 1])
        # 此时左指针不动，右指针对应的元素没有在集合中
        while rk + 1 < n and s[rk + 1] not in occ:
            # 不断地移动右指针
            occ.add(s[rk + 1])
            rk += 1
        # 当走到这里说明一次遍历结束，并且第一次出现了重复的字符
        # 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = max(ans, rk - i + 1)
    return ans

复杂度分析

• 时间复杂度：O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。
• 空间复杂度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0,128) 内的字符，即 ∣Σ∣=128。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)。