3.longest-substring-without-repeating-characters.md

题目地址(3. 无重复字符的最长子串)

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。   请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。 

前置知识

• 哈希表
• 滑动窗口

公司

• 阿里
• 字节
• 腾讯

思路

题目要求连续， 我们考虑使用滑动窗口。 而这道题就是窗口大小不固定的滑动窗口题目，然后让我们求满足条件的窗口大小的最大值，这是一种非常常见的滑动窗口题目。

算法：

用一个 hashmap 来建立字符和其出现位置之间的映射。同时维护一个滑动窗口，窗口内的都是没有重复的字符，去尽可能的扩大窗口的大小，窗口不停的向右滑动。

1. 如果当前遍历到的字符从未出现过，那么直接扩大右边界；

2. 如果当前遍历到的字符出现过，则缩小窗口（左边索引向右移动），然后继续观察当前遍历到的字符；

3. 重复（1）（2），直到窗口内无重复元素；

4. 维护一个全局最大窗口 res，每次用出现过的窗口大小来更新结果 res，最后返回 res 获取结果;

5. 最后返回 res 即可;

(图片来自： https://github.com/MisterBooo/LeetCodeAnimation)

关键点

• mapper 记录出现过并且没有被删除的字符
• 滑动窗口记录当前 index 开始的最大的不重复的字符序列

代码

代码支持：C++，Java，Python3

C++ Code:

classSolution { public:intlengthOfLongestSubstring(string s) { int ans = 0, start = 0; int n = s.length(); // map<char, int> mp; for(int i=0;i<n;i++) { char alpha = s[i]; if(mp.count(alpha)) { start = max(start, mp[alpha]+1); } ans = max(ans, i-start+1); // 字符位置 mp[alpha] = i; } return ans; } };

Java Code:

classSolution { publicintlengthOfLongestSubstring(Strings) { intans = 0, start = 0; intn = s.length(); //Map<Character, Integer> map = newHashMap<>(); for(inti=0;i<n;i++) { charalpha = s.charAt(i); if(map.containsKey(alpha)) { start = Math.max(start, map.get(alpha)+1); } ans = Math.max(ans, i-start+1); // 字符位置map.put(alpha, i); } returnans; } }

Python3 Code:

fromcollectionsimportdefaultdictclassSolution: deflengthOfLongestSubstring(self, s: str) ->int: l=0ans=0counter=defaultdict(lambda: 0) forrinrange(len(s)): whilecounter.get(s[r], 0) !=0: counter[s[l]] =counter.get(s[l], 0) -1l+=1counter[s[r]] +=1ans=max(ans, r-l+1) returnans

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。