Skip to content

Latest commit

 

History

History
156 lines (111 loc) · 4.06 KB

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

File metadata and controls

156 lines (111 loc) · 4.06 KB
Raw

题目地址(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 即可;

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 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。