具有非重复字符的最长子串 [英] Longest Substring with Non-Repeating Character

问题描述

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

I am trying to solve the problem of finding the longest substring without a repeating character from a given string.

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

我想我正确解决了这个问题：

I think I am solving it correctly:

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

Start a new substring when you encounter a repeated character.

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

But I am not getting the answers right?

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

In the above example the output is 5 whereas the correct answer is 6.

但是在这种情况下：

print（x.lengthOfLongestSubstring（ ababa））

print(x.lengthOfLongestSubstring("ababa"))

输出正确，即2。

不确定我为什么无法通过该案件？谢谢。

Not sure why am I failing that case? Thanks.

推荐答案

我对函数进行了一些更改，以返回最长的唯一字符子串，而不仅仅是长度。

I've changed your function a bit to return the longest substring of unique characters instead of just length of it. If you want length - you can always get that from string.

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，以构建一个char数组。

Code goes through each char building a char array.

如果在数组中已找到一个char，则会保留该数组的副本。 ，从它的开头一直剪切到该字符并继续构建它。

If it finds a char already in the array it keeps a copy of the array, cuts off beginning of it up to that character and keeps building it.

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

At the end it picks longest substring it found and returns it.

这篇关于具有非重复字符的最长子串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！