专栏首页编程理解Leetcode 3. 无重复字符的最长子串

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

题目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

解法

判断一个字符串是否包含重复字符,最简单的方式自然是将该字符串转为

集合,判断集合的

是否与字符串长度相等即可。因此可以设置

两个下标,二重循环判断所有子字符串,即可获得最长的不重复字符串长度。

这里找一种可以递推求出最长不重复子字符串长度的方式。不妨以

表示以第

个元素结尾的不重复子字符串,以

表示

的长度。以

表示第

个字符在

中的位置,若

,则表示第

个字符不在

中,有

,否则

因为

只与

相关,所以不妨定义

变量表示

函数值。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        ret,t,l=1,1,len(s)
        for i in range(1,l):
            p=s[i-t:i].find(s[i])
            t=t+1 if p==-1 else t-p
            ret=max(ret,t)
        return ret

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Leetcode 686. 重复叠加字符串匹配

    给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数,使得字符串B成为叠加后的字符串A的子串,如果不存在则返回 -1。

    zhipingChen
  • Leetcode 1029. 两地调度

    公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0],飞往 B 市的费用为 costs[i][1]。

    zhipingChen
  • Leetcode 136. 只出现一次的数字

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

    zhipingChen
  • 老司机开车,教会女朋友什么是「马拉车算法」

    马拉车算法( Manacher‘s Algorithm )是小吴最喜欢的算法之一,因为,它真的很牛逼!

    帅地
  • 老司机开车,教会女朋友什么是「马拉车算法」

    马拉车算法( Manacher‘s Algorithm )是小吴最喜欢的算法之一,因为,它真的很牛逼!

    五分钟学算法
  • 在AndroidStudio上搭建SVN

      在Eclipse上直接安装SVN插件即可,但是在AndroidStudio上不行,需要关联SVN客户端。并且安装command line的客户端才可以。co...

    饮水思源为名
  • 【Discuz】-QQ互联登陆提示错误信息:Unknown column 'conuintoken' in 'field list'

    Jackson0714
  • 【消息队列 MQ 专栏】消息队列之 Kafka

    Kafka 最早是由 LinkedIn 公司开发一种分布式的基于发布/订阅的消息系统,之后成为 Apache 的顶级项目。主要特点如下:

    芋道源码
  • 实操 | 内存占用减少高达90%,还不用升级硬件?没错,这篇文章教你妙用Pandas轻松处理大规模数据

    编译 | AI科技大本营(rgznai100) 参与 | 周翔 注:Pandas(Python Data Analysis Library) 是基于 Num...

    AI科技大本营
  • Python 批量合并多个txt文件

    py3study

扫码关注云+社区

领取腾讯云代金券