Hot100-无重复字符的最长子串

题目链接:Hot100-3. 无重复字符的最长子串

题目背景

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

输入输出示例

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

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

示例 3:

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

题目规模

提示：

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

解题思路

该题属于滑动窗口类型中的不定长滑动窗口，子类型为字符串越短越符合题意，找符合题意的最长字符串。具体总结链接见滑动窗口总结。

单调性分析：当子字符串变长时，字符重复的可能性就变大，就越不符合题意，故该题具有单调性。

对于越短越符合题意，找最长的子串的的不定长滑动窗口类型，通常用\(left,right\)代表窗口的左右两端。开始时固定\(left\)，移动\(right\)从头遍历整个字符串，当此时构成的窗口不符合题意时，移动\(left\)使窗口重新满足题意。

在移动的过程中，不断将当前符合题意的窗口大小和全局最优大小进行对比，判断是否有更符合题意的解。当前窗口大小为： \[ ans = right - left + 1 \] 想象一个大小为2的窗口即可理解该公式。

假设当前字符串为abcabcbb，从下图理解解题过程：

• ①刚开始时移动\(right\)，固定\(left\)，并在移动的过程逐步更新答案：

  

• ②当\(right\)移动时，不满足题意了，移动\(left\)至重新满足题意，并记录当前最优窗口大小：

  

• ③重复上列步骤:

  

  \(right\)指向\(b\)时，窗口不符合题意，重新移动\(left\)至其符合题意

  

  该例子\(left,right\)最后的状态如下图所示

  

具体代码

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        '''
        子数组越短越合法
        找最长的符合题意的子字符串长度
        '''
        #记录答案和左指针
        ans = left = 0
        #记录子字符串中的元素个数
        dics = DefaultDict(int)
        for right,i in enumerate(s):
            dics[i] += 1
            #说明不符合题意了
            while dics[i] > 1:
                dics[s[left]] -= 1
                left += 1
            #每次更新答案
            ans = max(ans,right - left + 1)
        return ans        

复杂度分析

• 时间复杂度：\(left,right\)均不回溯，一个元素最多被两个指针遍历，故时间复杂度是O(n)。
• 空间复杂度：定义了一个字典\(dics\),字典最多有字符串长度个数个元素，故空间复杂度是O(n)。