LeetCode Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring"pwke" is a subsequenceand not a substring.

解法1: 参考自LeetCode题解3:Longest Substring Without Repeating Characters

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        start=0
        max_length=0
        n=len(s)
        sub_str=''
        for end in range(n):
            if s[end] not in sub_str:
                sub_str+=s[end]
            else:
                max_length=max(max_length,len(sub_str))
                while s[start]!=s[end]:
                    start+=1
                start+=1
                sub_str=s[start:end+1]
        return max(max_length,len(sub_str))

解法2: 参考自LeetCode该题目提交中 sample 64 ms submission

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        chars = {}
        begin = 0
        result = 0
        for i, c in enumerate(s, 1):
            if (c in chars) and (chars[c] > begin):
                begin = chars[c]
            elif (i - begin > result):
                result = i - begin              
            chars[c] = i
        return result

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据处理

leetcode222求完全二叉树节点个数

3714
来自专栏计算机视觉与深度学习基础

Leetcode 258. Add Digits

Given a non-negative integer num, repeatedly add all its digits until the resul...

1995
来自专栏IT笔记

ArrayList和LinkedList的区别

首先来看ArrayList和LinkedList的集成类和接口的区别。 public class ArrayList<E> extends AbstractLi...

3248
来自专栏Android知识点总结

看得见的数据结构Android版之二分搜索树篇

964
来自专栏尾尾部落

[剑指offer] 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6...

1161
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(四)No.52

这是本坑的第四篇,之前已经说了关于 HashSet 、BitMap 、Bloom Filter 布隆过滤器了,本篇主要讲B-树。要是还不知道前面讲了啥的,可以点...

2067
来自专栏数据结构与算法

树链剖分详解

前言 树链剖分是什么? 树链剖分,说白了就是一种让你代码不得不强行增加1k的数据结构-dms 个人理解:+1:joy: 有什么用? 证明出题人非常毒瘤 ...

3207
来自专栏木子昭的博客

明星程序员被Google挂掉的故事

首先要提一个软件Homebrew Homebrew可能是Mac上最好用的包管理器, 地位相当于Ubuntu的apt, 也相当于命令行版的AppStore ? ...

3755
来自专栏aCloudDeveloper

算法导论第十八章 B树

一、高级数据结构   本章以后到第21章(并查集)隶属于高级数据结构的内容。前面还留了两章:贪心算法和摊还分析,打算后面再来补充。之前的章节讨论的支持动态数据集...

2096
来自专栏趣学算法

数据结构 第13讲 三元组 (F、C、L/R) 序列创建二叉树

/* 输入三元组 (F、C、L/R) 序列输入一棵二叉树的诸边(其中 F 表示双亲结点的标识,C 表示孩子结点标识,L/R...

3043

扫码关注云+社区

领取腾讯云代金券