队列、滑动窗口，面试官期待应聘者能够用基于循环的代码来避免不必要的重复计算。

题目

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

测试用例

功能测试（包含多个字符的字符串；只有一个字符的字符串；所有字符都唯一的字符串；所有字符都相同的字符串）。 特殊输入测试（空字符串）。

本题考点

考查应聘者用动态规划分析问题的能力。应聘者能够熟练应用动态规划分析问题是解答这道面试题的前提。 考查应聘者对递归及时间效率的理解。如果只是能够把递归分析转换为递归代码，则应聘者不一定能够通过这道题的面试。面试官期待应聘者能够用基于循环的代码来避免不必要的重复计算。

示例

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

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

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

提示：s.length <= 40000

考察知识点

队列、滑动窗口

核心思想

滑动窗口

遍历字符串，找到不重复的部分，记录下来，输出最长的那一个。

68747470733a2f2f626c6f672d313235373132363534392e636f732e61702d6775616e677a686f752e6d7971636c6f75642e636f6d2f626c6f672f76786137662e676966

动态规划

• 首先定义函数 \(f(i)\) 表示以第 \(i\) 个字符为结尾的不包含重复字符的子字符串的最大长度。初始化 \(f(0) = 1\)。
• 如果第 \(i\) 个字符在之前没有出现过，那么 \(f(i) = f(i) + 1\)。
• 如果第 \(i\) 个字符在之前已经出现过，那么先计算第 \(i\) 个字符距离它上次出现在字符串中的位置的距离，并记为 \(d\)。
  • 当 \(d <= f(i-1)\) 时，说明第 \(i\) 个字符上次出现在 \(f(i-1)\) 对应的最长子字符串之中。同时这也意味着在第 \(i\) 个字符出现两次所夹的子字符串中再也没有其他重复的字符了。所以，此时 \(f(i) = d\)。
  • 当 \(d>f(i-1)\) 时，说明第 \(i\) 个字符上次出现在 \(f(i-1)\) 对应的最长子字符串之前，因此仍然有 $ f(i)=f(i-1)+1$。

以 arabcacfr 为例：

更新选择

Update Type
0	\(f(0) = 1\)
1	\(f(i) = f(i) + 1\)
2	\(f(i) = d\)

运算过程

index	0	1	2	3	4	5	6	7	8
char	a	r	a	b	c	a	c	f	r
\(d\)	\	\	2	\	\	3	2	\	7
compute \(d\)	\	\	2-0	\	\	5-2	6-4	\	8-1
\(d <= f(i-1)\)	\	\	True	\	\	True	True	\	False
Update Type	0	1	2	1	1	2	2	1	1
\(f(i)\)	1	2	2	3	4	3	2	3	4

由上表可知， arabcacfr 中最长不含重复的子字符串为 rabc 和 acfr , 长度为4。

状态转移方程为 \[ f(i)=\begin{cases} 0, \quad i = 0 \\ f(i-1) + 1, \quad d > f(i-1) \\ d,\quad d \leq f(i-1) \end{cases} \]

Python代码

• 滑动窗口

class Solution:
    def lengthOfLongestSubstring(self, s):
        max_length = 0  # 开始位置
        d = {}  # 保存字符出现位置
        start = 0  # 当前最大字串的开始位置 也就是滑动窗口的左边缘
        for i in range(len(s)):
            if s[i] in d and start <= d[s[i]]: 
                # 如果该字符串出现过 且 当前最大字串的开始位置(start)小于等于该字符串之前出现的位置
                start = d[s[i]] + 1  # 当前重复字符串上一次出现位置的下一个位置 被设置为 新的最大字串搜寻开始位置 也就是滑动窗口的左边缘
            max_length = max(i-start+1, max_length)  # i-start+1(当前位置(i)减去滑动窗口左边缘的间距，也就是新字串的长度)
            d[s[i]] = i  # 全部计算完成之后，更新这个字串出现位置。
        return max_length

print("leet code accept!!!")
cases = ["abcabcbb", "bbbbb", "pwwkew", "aabaab!bb", "nfpdmpi", "dvdf"]
answer = ["abc", 'b', 'wke', "ab!", 'nfpdm', 'vdf']

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(cases)):
        print(solution.lengthOfLongestSubstring(cases[i])==len(answer[i]))

• 滑动窗口的另一个版本

class Solution3:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        from collections import defaultdict
        d = defaultdict(int)  # defaultdict本质就是一个dict
        l = ans = 0  # l是当前的最大长度
        for i,c in enumerate(s):
            while l > 0 and d[c] > 0:  # l>0说明不再是第一个字符 d[c]>0说明这个字符不是第一次出现
                # 下面这段while循环 会执行l次且直到将c的次数减为0 
                # 实际上就是把队列左边的元素移出去 平移整个
                d[s[i-l]] -= 1
                l -= 1  # 当前长度减去1
            d[c] += 1  # 记录最新发现的字符
            l += 1  # 记录最新长度
            ans = max(ans, l)
        return ans

• 动态规划

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 几种特判
        if len(s) == 1: return 1
        if s == " ": return 1
        if not s:  return 0

        # 初始换变量
        hash_map = {s[0]: 0}
        dp = [1]
        _max = 0
        
        # 开始动态规划
        for i in range(1, len(s)):
            char = s[i]
            if char in hash_map:
                d = i - hash_map[char]
                hash_map[char] = i
                if d > dp[-1]:
                    dp.append(dp[-1] + 1)
                else:
                    dp.append(d)
            else:
                hash_map[char] = i
                dp.append(dp[-1] + 1)
            if dp[-1] > _max:
                _max = dp[-1]
        
        return _max

类似问题

LeetCode 76. 最小覆盖子串