LeetCode08：无重复字符的最长子串

8.无重复字符的最长子串

题目

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

题解

我的解法

首先考虑特殊情况，如果字符串为空，结果为0

初始化一个字典lettersIndex ，用于存储字符和相应的索引；

初始化最长不重复子串的长度max_length ，0

初始化子串的起始索引start ，0

遍历字符串，获取每一个字符和其索引。

  • 检查当前字符，如果在字典中，并且字典中该字符的索引不小于start ，代表已经重复，更新start （该字符在字典中的索引加1，也就是起始索引加1），更新字典中该字符的索引为当前索引。

  • 遍历每一个字符，需要计算当前子串的长度，i - start + 1

  • 更新全局最大长度。max_length = max(max_length, current_length)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0

        lettersIndex = {}
        max_length = 0
        start = 0

        for i, char in enumerate(s):
            if char in lettersIndex and lettersIndex[char] >= start:
                start = lettersIndex[char] + 1

            lettersIndex[char] = i
            current_length = i - start + 1
            max_length = max(max_length, current_length)

        return max_length

官方题解

这种方法的核心思想是使用两个指针（左指针和右指针）来维护一个动态的窗口，窗口内的字符都是不重复的。通过不断移动这两个指针，可以找到最长的不重复子串。

  1. 初始化变量:
    • occ = set() 初始化一个集合，用于记录当前子串中出现的字符。
    • n = len(s) 获取字符串 s 的长度。
    • rk, ans = -1, 0 初始化右指针 rk 为 -1（表示在字符串左侧），初始化最长子串长度 ans 为 0。
  2. 遍历字符串:
    • for i in range(n): 遍历字符串 s 的每一个字符。
  3. 左指针移动:
    • if i != 0: 当不是第一个字符时，将左指针左侧的字符从集合中移除，从而缩小子串的范围。
  4. 右指针移动:
    • while rk + 1 < n and s[rk + 1] not in occ: 只要右指针右侧的字符不在当前集合中，就不断移动右指针，并将字符加入集合。
  5. 更新最长子串长度:
    • ans = max(ans, rk - i + 1) 更新最长不重复子串的长度。这里 rk - i + 1 表示从左指针 i 到右指针 rk 的子串长度。
  6. 返回结果:
    • return ans 返回最长不重复子串的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 哈希集合，记录每个字符是否出现过
        occ = set()
        n = len(s)
        # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        rk, ans = -1, 0
        for i in range(n):
            if 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