CS50面试题：最长无重复子串递归解法为何测试用例4不通过

问题背景 #

给定一个字符串，找出不含重复字符的最长子串的长度，例如字符串"abcabcbb"的最长无重复子串长度为3（对应"abc"等结果）。
递归解法实现时，多数测试用例运行符合预期，仅输入"pwwekf"时结果异常，输出错误结果"pwekf"，不符合子串连续的规则，预期正确最长长度为4。

原始代码 #

def find_longest_substring(string, longest=0):
    current_longest_string = ""
    
    for char, i in zip(string, range(len(string))):
        if char not in current_longest_string:
            current_longest_string = f'{current_longest_string}{char}'
        # 遇到重复字符时统计长度，从重复位置重新查找
        else:
            longest = len(current_longest_string) \
                if len(current_longest_string) > longest else longest
            find_longest_substring(string[i:], longest)

    longest = len(current_longest_string)
    return longest, current_longest_string


# 测试用例1
print(find_longest_substring("abcabcbb"))
# 测试用例2
print(find_longest_substring("bbbbb"))
# 测试用例3
print(find_longest_substring("abcdef"))
# 测试用例4
print(find_longest_substring("pwwekf"))
# 测试用例5
print(find_longest_substring(""))

原始代码运行输出：

(3, 'abc')
(1, 'b')
(6, 'abcdef')
(5, 'pwekf')
(0, '')

核心问题点 #

• 递归返回值未被接收：调用find_longest_substring(string[i:], longest)后未处理返回结果，递归层计算的更长长度直接被丢弃，仅保留当前层的计算结果
• 历史最长长度被覆盖：循环结束后直接将longest赋值为当前子串长度，完全忽略了之前已经记录的更长的历史长度值
• 子串拼接逻辑错误：遇到重复字符时未截断当前子串，跳过重复字符后继续拼接，导致生成的current_longest_string不符合连续子串的定义，才会出现"pwwekf"输入得到"pwekf"的错误结果

修复后代码 #

def find_longest_substring(string, longest=0):
    current_longest_string = ""

    for char, i in zip(string, range(len(string))):
        if char not in current_longest_string:
            current_longest_string = f'{current_longest_string}{char}'
        # 遇到重复字符时统计长度，从重复位置重新查找
        else:
            longest = len(current_longest_string) \
                if len(current_longest_string) > longest else longest
            longest_new = find_longest_substring(string[i:], longest)
            if longest_new > longest:
                longest = longest_new

    longest = max(len(current_longest_string), longest)
    return longest

修复后运行输出：

3
1
6
4
0

所有测试用例结果均符合预期。

内容的提问来源于stack exchange，提问作者p-a