寻找最长不重复子串

afishhhhh 发布于2019-07-25 12:03 / 1091人阅读

摘要：寻找最长不重复子串思路时间复杂度为遍历字符串，过程中将出现过的字符存入字典，为字符，为字符下标用保存遍历过程中找到的最大不重复子串的长度用保存最长子串的开始下标如果字符已经出现在字典中，更新的值如果字符不在字典中，更新的值代码本题以及其它

寻找最长不重复子串 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 subsequence and not a substring.

思路(时间复杂度为O(n))

遍历字符串，过程中将出现过的字符存入字典，key为字符，value为字符下标

用maxLength保存遍历过程中找到的最大不重复子串的长度

用start保存最长子串的开始下标

如果字符已经出现在字典中，更新start的值

如果字符不在字典中，更新maxLength的值

return maxLength

代码

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        start = maxLength = 0
        usedChar = {}

        for i in range(len(s)):
            if s[i] in usedChar and start <= usedChar[s[i]]:
                start = usedChar[s[i]] + 1
            else:
                maxLength = max(maxLength, i - start + 1)
            usedChar[s[i]] = i

        return maxLength

本题以及其它leetcode题目代码github地址: github地址

私有云云服务器最长公共子串 java最长相同子串寻找重复数字 c语言随机抽取不重复

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/38655.html

JS算法题之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一个字符，判断正负符号，若是英文直接返回，若数字则不取。回文数题目描述判断一个整数是否是回文数。回文数是指正序从左向右和倒序从右向左读都是一样的整数。 JS算法题之leetcode(1~10) 前言一直以来，前端开发的知识储备在数据结构以及算法层面是有所暂缺的，可能归根于我们的前端开发的业务性质，但是我认为任何的编程岗位都离不开数据结构以及算法。因此，我作为...

SoapEye 2019-08-26 10:44 评论0 收藏0
动态规划问题（2）——寻找最长公共子串

摘要：题目给定两个字符串求出它们的最长公共字串说明比如在单词和它们的最长公共子序列是。最长公共子串和最长公共子序列的区别。题目给定两个字符串,求出它们的最长公共字串 var str1=abcdefg; var str2=xyzabcd; 说明：比如在单词abcdefg和abcdefg它们的最长公共子序列是abcd。寻找最长子序列常用于遗传学中，用于使用核苷酸碱基的首字母对DNA的描述（这...

wushuiyong 2019-08-21 11:27 评论0 收藏0
网易2018校招前端笔试题解析

摘要：现在有一个给定的字符串中每个字符代表小易的某个砖块的颜色。例如那么小易有六种排列的结果其中只有和满足最多只有一对不同颜色的相邻砖块。输入描述输入包括一行四个整数以空格分割输出描述输出一个整数表示小易最多能独立生活多少天。前言：注意，网易校招笔试在牛客网进行，在这里使用js完成算法题时，不要写一个function() {}就认为完成了题目，那样通过率是0%(题主就是这样，估计笔试挂了。...

Baoyuan 2019-08-21 11:56 评论0 收藏0
前端中等算法-无重复字符的最长子串

摘要：无重复字符的最长子串难度中等描述给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。输入输出解释因为无重复字符的最长子串是，所以其长度为。无重复字符的最长子串难度：中等描述：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。样例：输入: abcabcbb 输出: 3 解释: 因为无重复字符的最长子串是 abc，所以其长度为 3。输入: bbbbb ...

hyuan 2019-08-26 10:40 评论0 收藏0
Leecode-3 Longest Substring Without Repeating Char

摘要：题目解析题目含义很简单，即求出没有字符重复的子字符串的长度。例如很明显就是个由完全重复字符组成的字符串，所以它的答案长度为。所以综合来看该算法的效率为。题目 Given a string, find the length of the longest substring without repeating characters. Example 1: Input: abcabcbbO...

luzhuqun 2019-08-16 13:49 评论0 收藏0