python - 具有非重复字符的最长子串

Question

我正在尝试解决从给定字符串中找到没有重复字符的最长子字符串的问题。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        start = 0
        mlen = -1
        cur_ = {}
        cur = 0

        while(start<len(s) and cur<len(s)):
            if s[cur] in cur_ and cur_[s[cur]] >= start:
                if cur - start > mlen:
                    mlen = cur - start
                start = cur_[s[cur]] + 1    
                cur_[s[cur]] = cur            
            else:
                cur_[s[cur]] = cur
                if cur - start > mlen:
                    mlen = cur - start
            cur = cur + 1            
        return mlen

x = Solution()
print(x.lengthOfLongestSubstring("abababcdef"))

我认为我正在正确解决它:

遇到重复字符时开始一个新的子串。

但我没有得到正确的答案？

在上面的例子中，输出是 5 而正确答案是 6。

但是对于这种情况:

打印(x.lengthOfLongestSubstring(“ababa”))

输出是正确的，即 2。

不确定为什么我会失败？谢谢。

Answer 1

我对您的函数做了一些更改，以返回唯一字符的最长子串，而不仅仅是它的长度。如果你想要长度——你总是可以从字符串中得到它。

def get_longest_substring(input):
    """
    :type input: str
    :rtype: str
    """

    current = []
    all_substrings = []
    for c in input:
        if c in current:
            all_substrings.append(''.join(current))
            cut_off = current.index(c) + 1
            current = current[cut_off:]
        current += c
    all_substrings.append(''.join(current))

    longest = max(all_substrings, key=len)
    return longest

longest = get_longest_substring("abababcdefc")
print(longest, len(longest))

代码遍历每个字符构建一个字符数组。

如果它发现数组中已有一个字符，它会保留数组的副本，切断它的开头直到该字符并继续构建它。

最后它选择它找到的最长子串并返回它。