首页 > 其他分享 >无重复字符的最长子串

无重复字符的最长子串

时间:2023-04-07 10:01:35浏览次数:39  
标签:子串 字符 重复 哈希 表中 最长 指针

题目描述

难度中等

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

解题步骤

双指针加哈希表解法,时间复杂度\(O(n)\)。先定义两个指针,一个指针指向当前最长不重复子串的头,令一个指向尾,通过两个指针维护哈希表,使哈希表中的元素没有重复字符。头指针向前移动过程中如果哈希表中没有当前字符,就将当前字符放入哈希表中,最长子串的长度就是当前头指针到尾指针的长度;如果在哈希表中,删除哈希表中从尾指针到重复元素位置的所有元素。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        num_dict = {}
        i, j = -1, 0
        longest = 0
        while j < len(s):
            index = num_dict.get(s[j], -1)
            if index ==  -1:
                num_dict[s[j]] = j
                if j - i > longest:
                    longest = j - i
                j += 1
            else:
                k = i + 1
                while k < index:
                    del(num_dict[s[k]])
                    k += 1
                i = k
                num_dict[s[j]] = j
                j += 1
        return longest

标签:子串,字符,重复,哈希,表中,最长,指针
From: https://www.cnblogs.com/crazypigf/p/17295045.html

相关文章

  • 算法题-第K个小子串
    第K小子串输入一个字符串s,s由小写英文字母组成,保证s长度小于等于5000并且大于等于1。在s的所有不同的子串中,输出字典序第k小的字符串。字符串中任意个连续的字符组成的子序列称为该字符串的子串。字母序表示英文单词在字典中的先后顺序,即先比较第一个字母,若第一个字......
  • 字符串学习笔记(一)
    一些定义:1.Border:如果一个字符串的某个前缀同与它长度相同的后缀完全相同,就称这个前缀(后缀)是这个字符串的一个Border.2.周期:如果一个字符串s满足对于任意的p<i\(\leqslant\)|s|,s[i]=s[i-p],则称p是字符串s的周期,一个字符串可能有很多个周期。3.循环节:在周期的......
  • c++字符串拆分
    1staticvoidSplitString(conststring&data,conststring&delim,2std::vector<string>*result){3std::string::size_typepos;4constintsize=data.size();56for(intindex=0;index<size;++index)......
  • WPF的控件字符串内容使用StringFormat进行字符串转换
    在WPF中TextBlock的Text有时内容只需要改变个别数字,而不需要所以内容都修改,这时候就要使用StringFormat, 如:<TextBlockText="Ihavexxxfriends"/>这里面的xxx是个变量,那在Binding时应该怎样写呢<TextBlockText="{BindingFirendNumber,StringFormat='Ihave{0}firends......
  • IO流--字符流写数据
    IO流是用来处理设备之间的数据传输的,诸如:文件的复制,上传下载文件Java中的流可以从不同的角度进行分类:-按照流的方向不同:分为输入流和输出流。-按照处理数据单位的不同:分为字节流和字符流。-按照功能不同:分为节点流和处理流要区分字符流和字节流,我们可以从类名来区分类名中包......
  • 函数-字符串函数
    函数:是指一段可以直接被另一段程序调用的程序或代码  代码:selectlpad('01',5,'-');/*lpad:字符串左填充---01*/selectrpad('01',5,'-');/*rpad:字符串右填充01---*/selecttrim('hellomysql');/*trim:去除头部和尾部的空格*/selectsubstring('he......
  • 列表中有整数、有特殊字符、有字母的排序问题
    列表中有整数、有特殊字符、有字母a=[2,1,3,5,4,'d','f','e','c','a','b','?','*','&']#定义一个函数defsort1(x):ifisinstance(x,int):  #判断传入的参数中是否有整数returnx #有整数返回整数本身......
  • c++ string类的字符在内存的储存位置
    1.数据<=16字节,在当前栈区#include<iostream>#include<stdio.h>#include<stdlib.h>usingnamespacestd;intmain(){stringtemp="123456789012345";//注意长度int*a=(int*)malloc(sizeof(int));intb=0;for(a......
  • [oeasy]python0128_unicode_字符集_character_set_八卦_星座
    unicode回忆上次内容中国的简体和繁体汉字字符数量都超级大彼此还认对方为乱码 如果有一种编码所有的字符都能编进去就好了中日韩(CJK)欧洲拼音梵文阿拉伯文卢恩字符等等等都包括进去 ​ 添加图片注释,不超过1......
  • Python小练习:处理字符串
    Python小练习:处理字符串作者:凯鲁嘎吉-博客园 http://www.cnblogs.com/kailugaji/介绍两种处理字符串的方式:1.将英语名词单数转化为复数形式(仅适用于一般形式),2.将字符串(带有下换线_)转化为驼峰化形式。1.word_test.py1#-*-coding:utf-8-*-2#Author:凯鲁嘎吉......