无重复字符的最长子串

1、题目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

2、题解

2.1 滑动窗口

  • 什么是滑动窗口?其实就是一个队列,比如例题中的 abcabcbb,进入这个队列(窗口)为 abc 满足题目要求,当再进入 a,队列变成了 abca,这时候不满足要求。所以,我们要移动这个队列!

  • 如何移动?

    • 我们只要把队列的左边的元素移出就行了,直到满足题目要求!
    • 一直维持这样的队列,找出队列出现最长的长度时候,求出解!
  • 时间复杂度:O(n)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
    if not s:return 0
    left = 0
    lookup = set()
    n = len(s)
    max_len = 0
    cur_len = 0
    for i in range(n):
    cur_len += 1
    while s[i] in lookup:
    lookup.remove(s[left])
    left += 1
    cur_len -= 1
    if cur_len > max_len:max_len = cur_len
    lookup.add(s[i])
    return max_len
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    class Solution {
    public int lengthOfLongestSubstring(String s) {
    if (s.length()==0) return 0;
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    int max = 0;
    int left = 0;
    for(int i = 0; i < s.length(); i ++){
    // 被判断的字符上一次出现的位置就在滑动窗口内,即 [i,j] 内, 则需要left改变位置,改变为该字符上次出现位置+1。也就是left = map.get(s.charAt(i)) + 1的情况
    if(map.containsKey(s.charAt(i))){
    left = Math.max(left,map.get(s.charAt(i)) + 1);
    }
    // 若不在滑动窗口内,则不用管。不用管是因为:窗口中字符串没有重复字符。窗口符合定义。所以left = left,表示这个窗口暂时不变
    // 更新字符最新一次出现的位置
    map.put(s.charAt(i),i);
    max = Math.max(max,i-left+1);
    }
    return max;

    }
    }