Longest Substring Without Repeat

Question:

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.

Solution:

方法一

我自己写了一个方法,时间复杂度为o(n^2)
思路是这样的
start为开始位置
end为结束位置
s为输入的字符串
看第i个字符是否在字串s[start,end]之间存在
如果不存在将end向后移动一位,并计算其长的res = end-start
当存在时冲突时,将start更新到第i个字符在s[start,end]出现的位置,并将end向后移动一位

Code:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        start = 0
        end = 0
        temp = -1
        res = 0

        for i in range(len(s)):
            for j in range(start,end):
                if(s[j]==s[i]):
                    temp = j+1
            if(temp == -1):
                end += 1
                res = max(res,end-start)
            else :
                start = temp
                end += 1
                temp = -1
        return res

方法二

网上看了一个方法,很有意思,时间复杂度是o(n),首先参数m为一个列表,大小为256,可以根据ascii存放字符串中每个字符对应的位置
例如:'aAb'->m[97] = 0 , m[65] = 1,m[98] = 2
res记录最大长度
start用于记录substring的起始位置
当s[i]第一次出现也就是m[ord(s[i])]==0
或者是s[i]多次出现,但是起始位置大于之前相同字符出现的位置的时候,对res进行更新
res = max(res,i-start+1)
反之更新start位置,将start更新到出现相同字符的位置上

Code:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        m = [0]*256
        res = 0
        start = 0
        for i in range(len(s)):
            c = ord(s[i])
            if (m[c] == 0 or m[c]<start):
                res = max(res,i+1-start)
            else:
                start = m[c]
            m[c] = i+1
        return res

参考文献:
[LeetCode] Longest Substring Without Repeating Characters 最长无重复子串