跳转至

3. 无重复字符的最长子串#

问题描述#

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

 

示例 1:


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

示例 2:


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

示例 3:


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

示例 4:


输入: s = ""
输出: 0

 

提示：

  • 0 <= s.length <= 5 * 104
  • s 由英文字母、数字、符号和空格组成

解题思路#

问题最终的结果就是要确定 \(i\) 和 \(j\)（\(0 \le i \le j \le n-1\)）。

所以最基本的方法就是：

  1. 枚举 \(i\) 和 \(j\) 的所有取值
  2. 判断区间 \([i,j]\) 内是否有重复元素
  3. 若没有，根据该区间长度更新最大长度
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        ans = 0
        for i in range(n):
            for j in range(i, n):
                v = set()
                for x in s[i : j + 1]:
                    if x in v:
                        break
                    else:
                        v.add(x)
                else:
                    ans = max(ans, j - i + 1)
        return ans

s1.png

结果超时。

在上述方法的计算过程中，实际上很多情况不用计算。

如 \(i=0\) 时，如果 \(s[0:j]\) 中存在重复元素，则 \(j\) 之后就不用计算了，肯定也重复了。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        ans = 0
        for i in range(n):
            v = set()
            for j in range(i, n):
                if s[j] in v:
                    ans = max(ans, j - i)
                    break
                else:
                    v.add(s[j])
            else:
                ans = max(ans, j + 1 - i)
        return ans

s2.png

上述方法中仍然存在无用的计算。

\[ \begin{cases} 0:&0&1&2&3&\dots&j&\dots&\dots&n-1 \\ 1:&&1&2&3&\dots&j&j+1&\dots&n-1 \\ 2:&&&2&3&\dots&\dots&\dots&\dots&n-1 \\ 3:&&&&3&\dots&\dots&\dots&\dots&n-1 \\ \end{cases} \]

如 \(i=0\) 时，\(s[0]\) 与 \(s[j]\) 首次重复，则当 \(i=1\) 时，\(s[1]\) 到 \(s[j]\) 显然都不重复，故直接可以从 \(j+1\) 开始判断，\(i\) 则变为重复的字符的下一个位置开始。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        ans, i, v = 0, 0, {}
        s = s + s[-1]  # 防止最后一次未被计算
        for j in range(len(s)):
            if s[j] in v and v[s[j]] >= i:
                ans = max(ans, j - i)
                i = v[s[j]] + 1
            v[s[j]] = j
        return ans

s3.png

返回顶部

在手机上阅读