在字符串python中查找最长的唯一子字符串

Question

我正在尝试寻找不包含重复字符的字符串的最长子字符串的古老问题（周围有很多版本）。我不知道为什么我的尝试不能正常工作：

def findLongest(inputStr):
    resultSet = []
    substr = []

    for c in inputStr:
        print ("c: ", c)
        if substr == []:
            substr.append([c])
            continue

        print(substr)
        for str in substr:
            print ("c: ",c," - str: ",str,"\n")
            if c in str:
                resultSet.append(str)
                substr.remove(str)
            else:
                str.append(c)
        substr.append([c])



    print("Result set:")
    print(resultSet)
    return max(resultSet, key=len)

print (findLongest("pwwkewambb"))

当我的输出到达第二个“w”时，它不会迭代所有 substr 元素。我想我做了一些愚蠢的事情，但我看不到它是什么所以一些指导将不胜感激！我觉得我要踢自己的答案......

我的输出的开头：

c:  p
c:  w
[['p']]
c:  w  - str:  ['p']

c:  w
[['p', 'w'], ['w']]
c:  w  - str:  ['p', 'w'] # I expect the next line to say c: w - str: ['w']

c:  k
[['w'], ['w']] # it is like the w was ignored as it is here
c:  k  - str:  ['w']

c:  k  - str:  ['w']
...

---

编辑：

我用

for idx, str in enumerate(substr):
    print ("c: ",c," - str: ",str,"\n")
    if c in str:
        resultSet.append(str)
        substr[idx] = []
    else:
        str.append(c)

并产生正确的结果。唯一的事情是空元素数组被设置为下一个字符。这似乎有点毫无意义；一定会有更好的办法。

我的预期输出是kewamb。

例如

c:  p
c:  w
[['p']]
c:  w  - str:  ['p']

c:  w
[['p', 'w'], ['w']]
c:  w  - str:  ['p', 'w']

c:  w  - str:  ['w']

c:  k
[[], [], ['w']]
c:  k  - str:  []

c:  k  - str:  []

c:  k  - str:  ['w']

c:  e
[['k'], ['k'], ['w', 'k'], ['k']]
c:  e  - str:  ['k']

c:  e  - str:  ['k']

c:  e  - str:  ['w', 'k']

c:  e  - str:  ['k']
...

Answer 1

根据@seymour 对错误回复的评论进行编辑：

def find_longest(s):
    _longest = set()
    def longest(x):
         if x in _longest:
             _longest.clear()
             return False
         _longest.add(x)
         return True
    return ''.join(max((list(g) for _, g in groupby(s, key=longest)), key=len))

并测试：

In [101]: assert find_longest('pwwkewambb') == 'kewamb'

In [102]: assert find_longest('abcabcbb') == 'abc'

In [103]: assert find_longest('abczxyabczxya') == 'abczxy'

旧答案：

from itertools import groupby

s = set() ## for mutable access

''.join(max((list(g) for _, g in groupby('pwwkewambb', key=lambda x: not ((s and x == s.pop()) or s.add(x)))), key=len))
'kewamb'

groupby返回一个根据key参数中提供的函数分组的迭代器，默认情况下为lambda x: x。我们不是使用默认的状态，而是通过使用可变结构来利用某种状态（如果使用普通函数，这可以通过更直观的方式完成）

lambda x: not ((s and x == s.pop()) or s.add(x))

这里发生的事情是因为我无法在 lambda 中重新分配全局赋值（我再次可以使用适当的函数来执行此操作），所以我刚刚创建了一个可以添加/删除的全局可变结构。关键（没有双关语）是我只通过使用短路根据需要添加/删除项目来保留我需要的元素。

max并且len是相当不言自明的，以获得最长的列表groupby

另一个没有可变全局结构业务的版本：

def longest(x):
     if hasattr(longest, 'last'):
         result = not (longest.last == x)
         longest.last = x
         return result
     longest.last = x
     return True


''.join(max((list(g) for _, g in groupby('pwwkewambb', key=longest)), key=len))
'kewamb'