Links

0003. 无重复字符的最长子串

题目地址(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. 1.
    如果当前遍历到的字符从未出现过,那么直接扩大右边界;
  2. 2.
    如果当前遍历到的字符出现过,则缩小窗口(左边索引向右移动),然后继续观察当前遍历到的字符;
  3. 3.
    重复(1)(2),直到窗口内无重复元素;
  4. 4.
    维护一个全局最大窗口 res,每次用出现过的窗口大小来更新结果 res,最后返回 res 获取结果;
  5. 5.
    最后返回 res 即可;
3.longestSubstringWithoutRepeatingCharacters
(图片来自: https://github.com/MisterBooo/LeetCodeAnimation)

关键点

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

代码

代码支持:C++,Java,Python3
C++ Code:
class Solution {
public:
int lengthOfLongestSubstring(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:
class Solution {
public int lengthOfLongestSubstring(String s) {
int ans = 0, start = 0;
int n = s.length();
//
Map<Character, Integer> map = new HashMap<>();
for(int i=0;i<n;i++)
{
char alpha = 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);
}
return ans;
}
}
Python3 Code:
from collections import defaultdict
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
l = 0
ans = 0
counter = defaultdict(lambda: 0)
for r in range(len(s)):
while counter.get(s[r], 0) != 0:
counter[s[l]] = counter.get(s[l], 0) - 1
l += 1
counter[s[r]] += 1
ans = max(ans, r - l + 1)
return ans
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。