题目描述

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

示例1

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

示例2

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

示例3

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例4

输入: s = ""
输出: 0

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

方法一：滑动窗口

复杂度

时间复杂度：O(N)，其中 NN 是字符串的长度。左指针和右指针分别会遍历整个字符串一次

思路

1、首先可以肯定，这个题目至少要对字符串从头到尾遍历一边。

2、可以创建一个存当前符合条件的子串的列表result_str，然后创建一个结果值result

3、判断当前字符是否存在于列表中，若存在则将该查到其索引，并将列表前面的元素全部删除（包括该字符）

4、在遍历字符串时将每个字符存入列表result_str中

5、获取一下新result_str的长度和result结果值比一下，若大于则result=len(result_list)，否则不变

代码

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        result =0
        result_str = []
        for i in s:
            if i in result_str:
                result_str = result_str[result_str.index(i)+1:]
            result_str.append(i)
            result=len(result_str)if len(result_str)>result else result
        return result

if __name__=='__main__':
    solution = Solution()
    print(solution.lengthOfLongestSubstring("abcabcbb"))
    print(solution.lengthOfLongestSubstring("bbbbb"))
    print(solution.lengthOfLongestSubstring("pwwkew"))
    print(solution.lengthOfLongestSubstring("aab"))

优化写法

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        result =0
        result_str = []
        for i in s:
            if i in result_str: result_str =result_str[result_str.index(i)+1:]
            result_str.append(i)
            result=max(len(result_str),result)
        return result

if __name__=='__main__':
    solution = Solution()
    print(solution.lengthOfLongestSubstring("abcabcbb"))
    print(solution.lengthOfLongestSubstring("bbbbb"))
    print(solution.lengthOfLongestSubstring("pwwkew"))
    print(solution.lengthOfLongestSubstring("aab"))