“无重复字符的最长子串（Longest Substring Without Repeating Characters）”问题的 Python3 解答

题目描述

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

示例

示例 1:

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

示例2：

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

示例3：

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

测试用例

abcabcbb    3
bbbbb   1
pwwkew  3
""      0
au      2
dvdf    3
cdd     2
ddc     2

解题思路

逐字符遍历字符串，记录第一个无重复子串s[0]。查看下一个字符是否被rStr所包含，不包含就将此字符加到rStr的末尾，直到找到一个已经包含在rStr中的字符，此时，这个无重复子串的长度就有了。依次方法，继续查找子串，并与当前已经找到的子串做比较，记录最长的子串长度即可。字符串遍历完毕，问题得解。

解答

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        sLen = len(s)
        if sLen < 1:
            return 0
        rLen = 1
        startIndex = 1
        endIndex = 0
        rStr = s[0]

        while startIndex != sLen != endIndex:
            for i in range(startIndex, sLen):
                if s[i] not in rStr:
                    endIndex = i + 1
                    rStr = s[startIndex - 1:endIndex]
                else:
                    break
            rLen = max(rLen, len(rStr))
            if startIndex != sLen:
                rStr = s[startIndex]
            startIndex = startIndex + 1
        return rLen

算法分析

上述算法用Python3实现的时候有一个边界问题，字符串为空的情况下长度为 0，返回此值即可，否则下面初始化第一个无重复子串就溢出了。

上述算法时间复杂度是O(n^2)，并不理想。

中文官网的题目地址：无重复字符的最长子串