LeetCode 3. 无重复字符的最长子串

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

网络异常,图片无法展示
|

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

leetcode-cn.com/problems/lo…

题目描述

给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
示例 4:
输入: s = ""
输出: 0
提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

思路

通过双指针和set检测是否有相同元素,有就左移set

代码

  • 语言支持:Python3

Python3 Code:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left,right = 0,0
        resMax = 0
        hashSet = set()
        # 通过双指针和set检测是否有相同元素,有就左移set
        while right < len(s):
            while s[right] in hashSet:
                hashSet.remove(s[left])
                left += 1
            hashSet.add(s[right])
            resMax = max(resMax, len(hashSet))
            # print(hashSet)
            right += 1
        return resMax

复杂度分析

令 n 为数组长度。

  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(n)O(n)
目录
相关文章
|
6天前
|
存储 算法 程序员
【Leetcode 程序员面试金典 01.01】判定字符是否唯一 —— 位运算|哈希表
可以使用哈希表或位运算来解决此问题:由题可知s[i]仅包含小写字母,int[26]即能表示字符的出现次数;
|
6天前
|
算法
LeetCode算法题---无重复字符的最长子串、寻找两个正序数组的中位数(三)
LeetCode算法题---无重复字符的最长子串、寻找两个正序数组的中位数(三)
41 0
|
6天前
|
网络协议
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
|
6天前
|
存储 算法 Go
LeetCode 第三题: 无重复字符的最长子串
  给定一个字符串,请你找出其中不含有重复字符的最长子串的长度。
|
6天前
【Leetcode 2707】字符串中的额外字符 —— 动态规划
1. 状态定义:把`s[i−1]`当做是额外字符,`d[i] = d[i−1] + 1` 2. 状态转移方程:遍历所有的`j(j∈[0,i−1])`,如果子字符串`s[j...i−1]`存在于`dictionary`中,那么`d[i] = min d[j] 3. 初始状态`d[0] = 0`,最终答案为`d[n]`
|
6天前
leetcode:3. 无重复字符的最长子串
leetcode:3. 无重复字符的最长子串
17 0
|
6天前
|
算法
leetcode:387. 字符串中的第一个唯一字符
leetcode:387. 字符串中的第一个唯一字符
13 0
|
6天前
|
存储 索引
力扣1445 连续字符
力扣1445 连续字符
23 0
|
6天前
|
算法 C++
【刷题】Leetcode 1609.奇偶树
这道题是我目前做过最难的题,虽然没有一遍做出来,但是参考大佬的代码,慢慢啃的感觉的真的很好。刷题继续!!!!!!
9 0