Python递归实现无重复最长子串时异常输出的原因排查

问题背景 #

我是编程新手，仅了解递归函数的基本概念，在尝试用递归解决LeetCode的「无重复字符的最长子串」问题时出现了异常输出。该问题要求输出给定字符串中无重复字符的最长连续子串的长度。

我的代码 #

def getmax(s):
    having = []
    length = 0
    highest = [0]
    
    for i in  s:
        if i not in having:

            length +=1
            having.append(i)
            
            print(having)
            
            highest.append(length)
            
            print(length)


            if s.index(i) == len(s)-1:
                print("DONE",max(highest))
                return max(highest)
   
        else:
            new_s = s[s.index(i)+1:]
            getmax(new_s)

            
print(getmax("ckilbkd"))

算法思路 #

• 逐步累加子串长度并记录到列表中，直到遇到重复字符；
• 此时递归调用函数，传入剔除重复字符之前部分的新字符串（例如输入"dvdf"时新字符串为"vdf"，输入"ckilbkd"时新字符串为"ilbkd"）；
• 若遍历到字符串末尾且无重复字符，则返回记录的最大长度，判断条件为s.index(i) == len(s)-1。

异常输出 #

针对输入"ckilbkd"，预期输出应为5（对应子串"ilbkd"），但调试时出现了如下异常输出：

['c'] 
1                          #starts with the c, length is now 1
['c', 'k']
2                          #unrepeated charcter length is 2 
['c', 'k', 'i']
3                          #unrepeated charcter length is 3
['c', 'k', 'i', 'l']
4                           #unrepeated charcter length is 4
['c', 'k', 'i', 'l', 'b']
5                           #unrepeated charcter length is 5
['i']
1                           #repeated charachter found, starts over with new_s = ilbkd, length is now 1
['i', 'l']
2                           #unrepeated charcter length is 2 
['i', 'l', 'b']
3                           #unrepeated charcter length is 3 
['i', 'l', 'b', 'k']
4                           #unrepeated charcter length is 4 
['i', 'l', 'b', 'k', 'd']
5                           #unrepeated charcter length is 5
DONE 5                      #Should stop HERE
['c', 'k', 'i', 'l', 'b', 'd']
6                           #Dont understand what's happening here
DONE 6
6

程序在输出"DONE 5"后继续执行，出现了不符合预期的having列表和输出结果。我希望了解该异常出现的原因，而非直接获得问题解法，恳请帮忙分析。

异常原因分析 #

1. 递归调用后未终止当前循环 #

当遇到重复字符触发else分支调用getmax(new_s)时，递归调用完成后，当前函数的for循环并不会停止，会继续处理原字符串中后续的字符。比如在输入"ckilbkd"中：

• 遍历到第二个'k'时，调用getmax("ilbkd")，这个递归函数执行完毕返回5后，原函数的for循环会继续处理下一个字符'd'；
• 此时'd'不在当前的having列表（['c','k','i','l','b']）中，所以会执行if分支，将'd'加入列表，长度累加为6，最终触发返回逻辑，输出错误的6。

2. s.index(i)的逻辑错误 #

str.index(i)返回的是字符i在字符串s中第一次出现的索引，而非当前遍历到的索引。在原字符串"ckilbkd"中：

• 当遍历到最后一个字符'd'时，s.index('d')确实等于len(s)-1（因为'd'只出现一次），所以触发了return；
• 但如果字符串中有重复字符，这个判断会失效，同时它也无法准确判断当前循环是否走到了字符串末尾。

3. 递归结果未被利用 #

递归调用getmax(new_s)会返回该子串的最长无重复长度，但原函数并没有将这个结果与当前记录的max(highest)做比较，也没有将递归结果作为当前函数的返回值。这导致递归的正确结果（5）被忽略，原函数继续执行自己的循环，最终返回了错误的6。

内容的提问来源于stack exchange，提问作者Abdulrhman Shaheen