LeetCode【0003】无重复字符的最宗子串

1 中文标题

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

• 输入:                                         s                            =                            "                            a                            b                            c                            a                            b                            c                            b                            b                            "                                  s = "abcabcbb"                     s="abcabcbb"
  
• 输出:                                         3                                  3                     3
  
• 表明: 因为无重复字符的最宗子串是                                         "                            a                            b                            c                            "                                  "abc"                     "abc"，所以其长度为                                         3                                  3                     3。
  

示例 2：

• 输入:                                         s                            =                            "                            b                            b                            b                            b                            b                            "                                  s = "bbbbb"                     s="bbbbb"
  
• 输出:                                         1                                  1                     1
  
• 表明: 因为无重复字符的最宗子串是                                         "                            b                            "                                  "b"                     "b"，所以其长度为                                         1                                  1                     1。
  

示例 3：

• 输入:                                         s                            =                            "                            p                            w                            w                            k                            e                            w                            "                                  s = "pwwkew"                     s="pwwkew"
  
• 输出:                                         3                                  3                     3
  
• 表明: 因为无重复字符的最宗子串是                                         "                            w                            k                            e                            "                                  "wke"                     "wke"，所以其长度为                                         3                                  3                     3。必须是子串 的长度，                                        "                            p                            w                            k                            e                            "                                  "pwke"                     "pwke" 是一个子序列，不是子串。
  

提示：

•                                         0                            ≤                            s                            .                            l                            e                            n                            g                            t                            h                            ≤                            5                            ∗                            1                                       0                               4                                            0 \leq s.length \leq 5 * 10^4                     0≤s.length≤5∗104
  
•                                         s                                  s                     s 由英笔墨母、数字、符号和空格构成
  

---

2 求解思绪

2.1 基础解法： 暴力解法

思绪
具体求解思绪：

• 外层循环
  
  
  
  • 遍历字符串的每个位置作为子串的起始位置
    
  • 确保考虑了所有可能的子串起点
    
  
  
• 内层循环
  
  
  
  • 从起始位置向后扩展，寻找最长的无重复子串
    
  • 利用集合检测字符是否重复
    
  • 碰到重复字符就制止当前子串的扩展
    
  
  

求解示例

1. 输入: "abcabcbb"
2. 第1轮(i=0):  # 外循环
3.     # 内循环
4.     - j=0: seen={'a'}, curr_len=1
5.     - j=1: seen={'a','b'}, curr_len=2
6.     - j=2: seen={'a','b','c'}, curr_len=3
7.     - j=3: 遇到'a'重复，break, max_len=3
9. 第2轮(i=1):
10.     - j=1: seen={'b'}, curr_len=1
11.     - j=2: seen={'b','c'}, curr_len=2
12.     - j=3: seen={'b','c','a'}, curr_len=3
13.     - j=4: 遇到'b'重复，break, max_len=3
15. ... 依此类推

复制代码

Python代码

1. class Solution:
2.     def lengthOfLongestSubstring(self, s: str) -> int:
3.         # 记录最长无重复子串的长度
4.         max_len = 0
5.         
6.         # 遍历字符串的每个字符作为起始位置
7.         for i in range(len(s)):
8.             # 用集合记录当前子串中出现过的字符
9.             seen = set()
10.             # 记录当前子串的长度
11.             curr_len = 0
12.             
13.             # 从起始位置向后遍历，直到找到重复字符或到达字符串末尾
14.             for j in range(i, len(s)):
15.                 # 如果当前字符已经在集合中，说明出现重复
16.                 if s[j] in seen:
17.                     break
18.                
19.                 # 将当前字符添加到集合中
20.                 seen.add(s[j])
21.                 # 当前子串长度加1
22.                 curr_len += 1
23.             
24.             # 更新最长无重复子串的长度
25.             max_len = max(max_len, curr_len)
26.         
27.         return max_len

复制代码

时空复杂度分析

• 时间复杂度分析：                                        O                            (                                       n                               2                                      )                                  O(n²)                     O(n2)
  
  
  
  • 外层循环：                                                  O                                  (                                  n                                  )                                          O(n)                           O(n)，遍历每个可能的起始位置
    
  • 内层循环：                                                  O                                  (                                  n                                  )                                          O(n)                           O(n)，最差情况下必要遍历到字符串末尾
    总复杂度：                                                  O                                  (                                  n                                  )                                  ∗                                  O                                  (                                  n                                  )                                  =                                  O                                  (                                               n                                     2                                              )                                          O(n) * O(n) = O(n²)                           O(n)∗O(n)=O(n2)
    
  
  
• 空间复杂度分析：                                        O                            (                            m                            i                            n                            (                            m                            ,                            n                            )                            )                                  O(min(m,n))                     O(min(m,n))
  
  
  
  •                                                   m                                          m                           m是字符集巨细（如                                                  A                                  S                                  C                                  I                                  I                                          ASCII                           ASCII字符集为                                                  128                                          128                           128）
    
  •                                                   n                                          n                           n是字符串长度
    
  • 集合巨细不会超过                                                  m                                  i                                  n                                  (                                  m                                  ,                                  n                                  )                                          min(m,n)                           min(m,n)
    
  • 其他变量（max_len, curr_len等）：                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)
    
  
  

---

2.2 优化解法： 动态规划解法

思绪
（1）动态规划状态

•                                         d                            p                            [                            i                            ]                                  dp                     dp: 以第                                        i                                  i                     i个字符结尾的最长无重复子串的长度
  
•                                         l                            a                            s                            t                            _                            p                            o                            s                            [                            c                            h                            a                            r                            ]                                  last\_pos[char]                     last_pos[char]: 字符                                        c                            h                            a                            r                                  char                     char最后一次出现的位置
  

（2）状态转移方程

1. if s[i] 未出现过:
2.     dp[i] = dp[i-1] + 1
3. else:
4.     dp[i] = min(dp[i-1] + 1, i - last_pos[s[i]])

复制代码

示例

1. 输入: "abcabcbb"
2. 初始化：dp[0] = 1, last_pos['a'] = 0
4. i=1: 'b'
5. - 未出现过
6. - dp[1] = dp[0] + 1 = 2
7. - last_pos['b'] = 1
9. i=2: 'c'
10. - 未出现过
11. - dp[2] = dp[1] + 1 = 3
12. - last_pos['c'] = 2
14. i=3: 'a'
15. - 出现过，上次在位置0
16. - dp[3] = min(dp[2] + 1, 3 - 0) = min(4, 3) = 3
17. - last_pos['a'] = 3
19. ... 依此类推

复制代码

python代码

1. class Solution:
2.     def lengthOfLongestSubstring(self, s: str) -> int:
3.         # 处理空字符串情况
4.         if not s:
5.             return 0
6.             
7.         # dp[i]表示以s[i]结尾的最长无重复子串的长度
8.         dp = [0] * len(s)
9.         
10.         # 记录每个字符最后一次出现的位置
11.         last_pos = {}
12.         
13.         # 初始化第一个字符
14.         dp[0] = 1
15.         last_pos[s[0]] = 0
16.         max_len = 1
17.         
18.         # 从第二个字符开始遍历
19.         for i in range(1, len(s)):
20.             # 当前字符之前没有出现过
21.             if s[i] not in last_pos:
22.                 # 直接在前一个状态的基础上加1
23.                 dp[i] = dp[i-1] + 1
24.             else:
25.                 # 当前字符之前出现过，需要比较两个长度：
26.                 # 1. 前一个状态的长度加1
27.                 # 2. 当前位置与该字符上次出现位置的距离
28.                 dp[i] = min(dp[i-1] + 1, i - last_pos[s[i]])
29.             
30.             # 更新字符最后出现的位置
31.             last_pos[s[i]] = i
32.             # 更新最大长度
33.             max_len = max(max_len, dp[i])
34.         
35.         return max_len

复制代码

时空复杂度分析

• 时间复杂度分析：                                        O                            (                            n                            )                                  O(n)                     O(n)
  
  
  
  • 只必要遍历字符串一次
    
  • 每个位置的状态转移是                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)操作
    
  • 哈希表的查询和更新也是                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)
    
  
  
• 空间复杂度分析：
  
  
  
  • dp数组：                                                  O                                  (                                  n                                  )                                          O(n)                           O(n)，                                                  n                                          n                           n是字符串长度
    
  • last_pos哈希表：                                                  O                                  (                                  m                                  i                                  n                                  (                                  m                                  ,                                  n                                  )                                  )                                          O(min(m,n))                           O(min(m,n))，                                                  m                                          m                           m是字符集巨细，                                                  n                                          n                           n是字符串长度
    
  • 最多存储                                                  m                                  i                                  n                                  (                                  m                                  ,                                  n                                  )                                          min(m,n)                           min(m,n)个字符
    
  
  

总空间复杂度：                                   O                         (                         n                         +                         m                         i                         n                         (                         m                         ,                         n                         )                         )                         =                         O                         (                         n                         )                              O(n + min(m,n)) = O(n)                  O(n+min(m,n))=O(n)
算法优化

• 可以只保存前一个状态，将空间优化到O(1)
  
• 可以利用数组取代哈希表（如果字符集较小）
  
• 可以提前停止
  

1. class Solution:
2.     def lengthOfLongestSubstring(self, s: str) -> int:
3.         # 获取字符串长度
4.         n = len(s)
5.         
6.         # 特殊情况处理
7.         # 1. 空字符串或单个字符，直接返回长度
8.         if n <= 1:
9.             return n
10.         # 2. 如果所有字符都不相同，直接返回字符串长度
11.         if len(set(s)) == n:
12.             return n
13.             
14.         # 使用数组代替哈希表记录字符最后出现的位置
15.         # ASCII字符集大小为128，初始化为-1表示字符未出现过
16.         last_pos = [-1] * 128
17.         
18.         # prev_len：记录以前一个字符结尾的最长无重复子串长度
19.         prev_len = 1
20.         # max_len：记录全局最长无重复子串长度
21.         max_len = 1
22.         
23.         # 初始化第一个字符的位置
24.         last_pos[ord(s[0])] = 0
25.         
26.         # 从第二个字符开始遍历
27.         for i in range(1, n):
28.             # 提前终止优化
29.             # 如果剩余的字符长度加上当前长度小于已找到的最大长度
30.             # 则不可能找到更长的无重复子串，可以直接结束
31.             if max_len >= n - i + prev_len:
32.                 break
33.                
34.             # 获取当前字符的ASCII码
35.             char_idx = ord(s[i])
36.             
37.             # 计算当前以s[i]结尾的最长无重复子串长度
38.             if last_pos[char_idx] == -1:
39.                 # 情况1：当前字符从未出现过
40.                 # 直接在前一个长度基础上加1
41.                 curr_len = prev_len + 1
42.             else:
43.                 # 情况2：当前字符之前出现过
44.                 # 需要比较两个长度：
45.                 # a. 前一个长度加1
46.                 # b. 当前位置与该字符上次出现位置的距离
47.                 curr_len = min(prev_len + 1, i - last_pos[char_idx])
48.             
49.             # 更新字符最后出现的位置
50.             last_pos[char_idx] = i
51.             
52.             # 更新全局最大长度
53.             max_len = max(max_len, curr_len)
54.             
55.             # 更新前一个长度，用于下一轮计算
56.             prev_len = curr_len
57.             
58.         return max_len

复制代码

---

2.3 最优解法：滑动窗口

思绪
（1）滑动窗口

• 窗口范围：[left, right]
  
• window字典：记录窗口内每个字符的最新位置
  
• 窗口内的子串：包管无重复字符
  

（2）窗口滑动机制

• 当碰到重复字符时：
  
  
  
  • 左边界移动到重复字符前次出现位置的下一位
    
  • 确保左边界只能向右移动（不回退）
    
  
  
• 当碰到新字符时：
  
  
  
  • 直接扩展右边界
    
  • 更新字符位置
    
  
  

示例

1. 输入: "abcabcbb"
2. 初始状态：left=0, right=0, window={}
4. 1. 处理'a':
5.    window={'a':0}, left=0, right=0, max_len=1
7. 2. 处理'b':
8.    window={'a':0, 'b':1}, left=0, right=1, max_len=2
10. 3. 处理'c':
11.    window={'a':0, 'b':1, 'c':2}, left=0, right=2, max_len=3
13. 4. 处理'a':
14.    发现重复，left更新为1
15.    window={'a':3, 'b':1, 'c':2}, left=1, right=3, max_len=3
17. ...依此类推

复制代码

python代码

1. class Solution:
2.     def lengthOfLongestSubstring(self, s: str) -> int:
3.         # 用字典维护字符最后出现的位置
4.         window = {}
5.         # 记录最长无重复子串的长度
6.         max_len = 0
7.         # 滑动窗口的左边界
8.         left = 0
9.         
10.         # 遍历字符串，right为滑动窗口的右边界
11.         for right, char in enumerate(s):
12.             # 如果当前字符已在窗口中，需要更新左边界
13.             # 取max是为了确保left不会回退
14.             if char in window:
15.                 left = max(left, window[char] + 1)
16.             
17.             # 计算当前无重复子串的长度并更新最大长度
18.             curr_len = right - left + 1
19.             max_len = max(max_len, curr_len)
20.             
21.             # 更新字符最后出现的位置
22.             window[char] = right
23.         
24.         return max_len

复制代码

时空复杂度分析

• 时间复杂度分析：                                        O                            (                            n                            )                                  O(n)                     O(n)
  
  
  
  • 遍历字符串：                                                  O                                  (                                  n                                  )                                          O(n)                           O(n)
    
  • 字典操作（查找/插入）：                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)
    
  • 更新左边界：                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)
    
  • 计算长度：                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)
    
  
  
• 空间复杂度分析：                                        O                            (                            m                            i                            n                            (                            m                            ,                            n                            )                            )                                  O(min(m,n))                     O(min(m,n))
  
  
  
  • window字典空间：                                                  m                                  i                                  n                                  (                                  m                                  ,                                  n                                  )                                          min(m,n)                           min(m,n)空间，                                                  m                                          m                           m是字符集巨细（如ASCII为128），                                                  n                                          n                           n是字符串长度
    
  • 其他变量（left, right, max_len）：                                                  O                                  (                                  1                                  )                                          O(1)                           O(1)
    
  
  

基于滑动窗口的方法实现简单，代码逻辑清楚，不像动态规划代码复杂，逻辑复杂

---

3 标题总结

标题难度：中等
数据布局： 哈希表、字符串
应用算法： 动态规划、滑动窗口

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。