# \[3]\[中等]\[滑动窗口] 无重复字符的最长子串

## 题目描述

[3. 无重复字符的最长子串](https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/) [剑指 Offer 48. 最长不含重复字符的子字符串](https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/)

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

示例 1:

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

示例 2:

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

示例 3:

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

## 解题思路

### 我的思路

1. 首先使用一个滑动窗口, 或者是双指针, 始终指示着当前最长的无重复子串的开始和结尾
2. 对当前的字符(还未判断)进行判断, 是否能够使目前的无重复子串长度+1
   * 比较快的判断方法, 就是把目前无重复子串中的每一个字符加入到一个**集合**(set)当中, 就能用$$O(1)$$的时间进行判断了
   * 如果当前字符不在集合中, 那么无重复子串可以延长, 并把这个字符加入到集合中
3. 如果当前字符在集合中, 无重复子串中已经包含了这个字符, 则不能延长, 需要考虑抛弃子串中的部分内容, 抛弃的内容即为**子串的第一个字符到这个重复的字符(包含)**. 因此需要有一个指针一直指向子串的第一个字符, 然后滑动抛弃.

这样的时间复杂度为$$O(n)$$, $$n$$为字符串的长度.

对应的代码为:

```python
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0

        temp_set, max_len = set(), 0
        start = 0
        for i in range(n):
            if s[i] not in temp_set:
                temp_set.add(s[i])
                if len(temp_set) > max_len:
                    max_len = len(temp_set)
            else:
                while s[start] != s[i]:
                    temp_set.remove(s[start])
                    start += 1
                start += 1

        return max_len
```