Longest Substring Without Repeating Characters

问题描述

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

示例

• Example 1:

Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

• Example 2:

Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

• Example 3:

Input: “pwwkew”
Output: 3
Explanation: 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.

算法思路

该问题可以简化成查找一个字符串中最长的不重复字符子串，返回子串的长度。第一种方法用到了枚举和字典，感觉有点绕，我没有理解清楚；第二种方法采用了字符串的split方法，很巧妙，不过比较难想到。两种方法相比，第二种方法运行时间更短（84ms < 88ms）,推荐使用第二种方法，感兴趣的朋友可以研究下第一种方法。

方法一：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        dic, res, start, = {}, 0, 0
        for i, ch in enumerate(s):
            # when char already in dictionary
            if ch in dic:
                # check length from start of string to index
                res = max(res, i-start)
                # update start of string index to the next index
                start = max(start, dic[ch]+1)
            # add/update char to/of dictionary 
            dic[ch] = i
        # answer is either in the begining/middle OR some mid to the end of string
        return max(res, len(s)-start)

方法二：

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        maxnum,num,ss =0,0,''
        for each in s:
            if each in ss:
                ss = ss.split(each)[-1]+each # ‘’+each
                num =len(ss)
            else:
                num += 1
                ss += each
                if num>=maxnum:
                    maxnum = num
        return maxnum

参考资料

1. https://www.w3schools.com/python/ref_string_split.asp Python String split() Method
2. https://leetcode.com/problems/longest-substring-without-repeating-characters/ longest-substring-without-repeating-characters