算法：无重复字符的最长子串

发表于 分类于 Disqus：

题目

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

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

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func lengthOfLongestSubstring(_ s: String) -> Int {
  var maxLength = 0
  var left = 0
  var dict = [Character: Int]()
  for (i, char) in s.enumerated() {
    if let index = dict[char] {
      left = max(left, index + 1)
    }
    dict [char] = i
    maxLength = max(maxLength, i - left + 1)
  }

  return maxLength
}

解题思路

  1. 滑动窗口的思想

我们使用滑动窗口方法维护一个当前不含重复字符的子串。通过两个指针（这里用变量 left 表示窗口左边界，i 表示当前字符的索引），不断更新窗口的范围。

  1. 使用哈希字典记录字符位置

定义一个字典 dict 用来存储每个字符最后一次出现的位置。这样，当遇到重复字符时，就可以根据该字符上一次出现的位置，决定如何移动窗口左边界。

  1. 更新窗口边界

对于每个遍历到的字符 char：

  • 如果该字符已经存在于字典中，则说明窗口内出现了重复字符。此时更新 left 为 index + 1 和当前 left 的较大值，确保窗口内不包含重复字符。

  • 然后更新 dict[char] 为当前的索引 i。

  1. 计算最长子串长度

每次移动窗口后，通过 i - left + 1 计算当前窗口的长度，并与当前记录的最大长度进行比较，更新最大值。

  1. 时间复杂度与空间复杂度

由于我们只需遍历一次字符串，并在遍历过程中通过哈希表进行常数时间的查找操作，因此算法的时间复杂度为 O(n)，空间复杂度为 O(n)（最坏情况下哈希表中存储所有不同的字符）。

这种方法巧妙地利用滑动窗口和哈希表，能够在一次遍历中完成题目的要求，既保证了算法的效率，又使得代码逻辑清晰易懂。