具有非重复Ch的最长子串

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

我可以给你推荐一个简单的算法：

1。将所有变量设置为空。在

2.对于字符串中的每个字母ch：

2.1.检查当前找到的子字符串的dict中是否存在ch？在

如果是- 检查cur'子字符串是否长于max（maxSubStr初始化为“”）？，是否在max中-seve cur'子字符串。将当前找到的子字符串的dict设置为值ch，并将当前子字符串设置为ch。在

如果没有- 将ch添加到current found子字符串的dict。并用ch连接cur'子串。在

3。返回当前子串中最长的长度和最大值

class Solution(object):

def lengthOfLongestSubstring(self, s):
    """
    :type s: str
    :rtype: int
    """

    curSubStr = ""
    curSubStrDict = {}
    maxSubStr = ""
    for ch in s :
        if ch in curSubStrDict :
            if len(maxSubStr) < len(curSubStr):
                maxSubStr = curSubStr
            curSubStrDict = {}
            curSubStrDict[ch] = ch
            curSubStr = ""+ch

        else :
            curSubStrDict[ch] = ch
            curSubStr += ch

    return len(curSubStr) if len(curSubStr) > len(maxSubStr) else len(maxSubStr)

x = Solution()
print(x.lengthOfLongestSubstring("abcaabccdefgfgh")) # 5 = |cdefg|
print(x.lengthOfLongestSubstring("abababcdef")) # 6 = |abcdef|

就像在数组中查找max元素一样，我们“迭代”（而不是实际迭代）子字符串，而不重复char-并保存最长的。在

当我们检测到当前子字符串中包含的字符时，就会发生迭代。然后迭代到下一个子串。在

Answer 2

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

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))

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

如果它发现数组中已经有一个char，它会保留一个数组的副本，将它的开头截断到该字符，然后继续构建它。在

最后，它选择找到的最长的子字符串并返回它。在

Answer 3

您在else分支中更新mlen错误，忘记添加当前字符。此外，遇到重复时，您不需要更新mlen：

if s[cur] in cur_ and cur_[s[cur]] >= start:
    start = cur_[s[cur]] + 1    
else:
    mlen = max(mlen, cur - start + 1)

cur_[s[cur]] = cur
cur = cur + 1