Skip to main content

3、无重复字符的最长子串

问题​

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

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

示例 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 由英文字母、数字、符号和空格组成

答案​

求一个数组中的满足某个要求的子集，优先考虑滑动窗口。

Solution.swift
class Solution {
     func lengthOfLongestSubstring(_ s: String) -> Int {
        if s.isEmpty { return 0 } //如果为空，直接返回
        var window = [Character]() //定义窗口
        var maxLength = 0
         s.forEach { value in
             if window.contains(value) == false {//如果没包含，扩大窗口
                 window.append(value)
             } else {
                 //包含了,说明找到了一个满足要求的子集，
                 //但是不能确定窗口范围外是否还有更大的满足要求的子集
                 //所以，缩小窗口到刚好不满足的情况，再扩大窗口
                 let idx = window.firstIndex(of: value)!
                 window.removeFirst(idx + 1)
                 window.append(value)
             }
             //更新maxLength
             maxLength = max(maxLength, window.count)
         }
         return maxLength
    }
}