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

1 中文题目

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

示例 1：

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

示例 2：

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

示例 3：

• 输入: $s="pwwkew"$
• 输出: $3$
• 解释: 因为无重复字符的最长子串是 $"wke"$，所以其长度为 $3$。必须是子串 的长度，$"pwke"$ 是一个子序列，不是子串。

提示：

• $0\le s.length\le 5\ast 10^4$
• $s$ 由英文字母、数字、符号和空格组成

---

2 求解思路

2.1 基础解法： 暴力解法

思路
详细求解思路：

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

求解示例

输入: "abcabcbb"
第1轮(i=0):  # 外循环
    # 内循环
    - j=0: seen={'a'}, curr_len=1
    - j=1: seen={'a','b'}, curr_len=2
    - j=2: seen={'a','b','c'}, curr_len=3
    - j=3: 遇到'a'重复，break, max_len=3

第2轮(i=1):
    - j=1: seen={'b'}, curr_len=1
    - j=2: seen={'b','c'}, curr_len=2
    - j=3: seen={'b','c','a'}, curr_len=3
    - j=4: 遇到'b'重复，break, max_len=3

... 依此类推

Python代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 记录最长无重复子串的长度
        max_len = 0
        
        # 遍历字符串的每个字符作为起始位置
        for i in range(len(s)):
            # 用集合记录当前子串中出现过的字符
            seen = set()
            # 记录当前子串的长度
            curr_len = 0
            
            # 从起始位置向后遍历，直到找到重复字符或到达字符串末尾
            for j in range(i, len(s)):
                # 如果当前字符已经在集合中，说明出现重复
                if s[j] in seen:
                    break
                
                # 将当前字符添加到集合中
                seen.add(s[j])
                # 当前子串长度加1
                curr_len += 1
            
            # 更新最长无重复子串的长度
            max_len = max(max_len, curr_len)
        
        return max_len

时空复杂度分析

• 时间复杂度分析：$O(n^2)$
  • 外层循环：$O(n)$，遍历每个可能的起始位置
  • 内层循环：$O(n)$，最差情况下需要遍历到字符串末尾
    总复杂度：$O(n)\ast O(n)=O(n^2)$
• 空间复杂度分析：$O(min(m,n))$
  • $m$是字符集大小（如$ASCII$字符集为$128$）
  • $n$是字符串长度
  • 集合大小不会超过$min(m,n)$
  • 其他变量（max_len, curr_len等）：$O(1)$

---

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

思路
（1）动态规划状态

• $dp[i]$: 以第$i$个字符结尾的最长无重复子串的长度
• $last\_pos[char]$: 字符$char$最后一次出现的位置

（2）状态转移方程

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

示例

输入: "abcabcbb"
初始化：dp[0] = 1, last_pos['a'] = 0

i=1: 'b'
- 未出现过
- dp[1] = dp[0] + 1 = 2
- last_pos['b'] = 1

i=2: 'c'
- 未出现过
- dp[2] = dp[1] + 1 = 3
- last_pos['c'] = 2

i=3: 'a'
- 出现过，上次在位置0
- dp[3] = min(dp[2] + 1, 3 - 0) = min(4, 3) = 3
- last_pos['a'] = 3

... 依此类推

python代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 处理空字符串情况
        if not s: 
            return 0
            
        # dp[i]表示以s[i]结尾的最长无重复子串的长度
        dp = [0] * len(s)
        
        # 记录每个字符最后一次出现的位置
        last_pos = {}
        
        # 初始化第一个字符
        dp[0] = 1
        last_pos[s[0]] = 0
        max_len = 1
        
        # 从第二个字符开始遍历
        for i in range(1, len(s)):
            # 当前字符之前没有出现过
            if s[i] not in last_pos:
                # 直接在前一个状态的基础上加1
                dp[i] = dp[i-1] + 1
            else:
                # 当前字符之前出现过，需要比较两个长度：
                # 1. 前一个状态的长度加1
                # 2. 当前位置与该字符上次出现位置的距离
                dp[i] = min(dp[i-1] + 1, i - last_pos[s[i]])
            
            # 更新字符最后出现的位置
            last_pos[s[i]] = i
            # 更新最大长度
            max_len = max(max_len, dp[i])
        
        return max_len

时空复杂度分析

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

总空间复杂度：$O(n+min(m,n))=O(n)$

算法优化

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

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 获取字符串长度
        n = len(s)
        
        # 特殊情况处理
        # 1. 空字符串或单个字符，直接返回长度
        if n <= 1:
            return n
        # 2. 如果所有字符都不相同，直接返回字符串长度
        if len(set(s)) == n:
            return n
            
        # 使用数组代替哈希表记录字符最后出现的位置
        # ASCII字符集大小为128，初始化为-1表示字符未出现过
        last_pos = [-1] * 128
        
        # prev_len：记录以前一个字符结尾的最长无重复子串长度
        prev_len = 1
        # max_len：记录全局最长无重复子串长度
        max_len = 1
        
        # 初始化第一个字符的位置
        last_pos[ord(s[0])] = 0
        
        # 从第二个字符开始遍历
        for i in range(1, n):
            # 提前终止优化
            # 如果剩余的字符长度加上当前长度小于已找到的最大长度
            # 则不可能找到更长的无重复子串，可以直接结束
            if max_len >= n - i + prev_len:
                break
                
            # 获取当前字符的ASCII码
            char_idx = ord(s[i])
            
            # 计算当前以s[i]结尾的最长无重复子串长度
            if last_pos[char_idx] == -1:
                # 情况1：当前字符从未出现过
                # 直接在前一个长度基础上加1
                curr_len = prev_len + 1
            else:
                # 情况2：当前字符之前出现过
                # 需要比较两个长度：
                # a. 前一个长度加1
                # b. 当前位置与该字符上次出现位置的距离
                curr_len = min(prev_len + 1, i - last_pos[char_idx])
            
            # 更新字符最后出现的位置
            last_pos[char_idx] = i
            
            # 更新全局最大长度
            max_len = max(max_len, curr_len)
            
            # 更新前一个长度，用于下一轮计算
            prev_len = curr_len
            
        return max_len

---

2.3 最优解法：滑动窗口

思路
（1）滑动窗口

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

（2）窗口滑动机制

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

示例

输入: "abcabcbb"
初始状态：left=0, right=0, window={}

1. 处理'a':
   window={'a':0}, left=0, right=0, max_len=1

2. 处理'b':
   window={'a':0, 'b':1}, left=0, right=1, max_len=2

3. 处理'c':
   window={'a':0, 'b':1, 'c':2}, left=0, right=2, max_len=3

4. 处理'a':
   发现重复，left更新为1
   window={'a':3, 'b':1, 'c':2}, left=1, right=3, max_len=3

...依此类推

python代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 用字典维护字符最后出现的位置
        window = {}
        # 记录最长无重复子串的长度
        max_len = 0
        # 滑动窗口的左边界
        left = 0
        
        # 遍历字符串，right为滑动窗口的右边界
        for right, char in enumerate(s):
            # 如果当前字符已在窗口中，需要更新左边界
            # 取max是为了确保left不会回退
            if char in window:
                left = max(left, window[char] + 1)
            
            # 计算当前无重复子串的长度并更新最大长度
            curr_len = right - left + 1
            max_len = max(max_len, curr_len)
            
            # 更新字符最后出现的位置
            window[char] = right
        
        return max_len

时空复杂度分析

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

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

---

3 题目总结

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

原文地址：https://blog.csdn.net/qq_32882309/article/details/143655046

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！