如何高效查找无重复字符的最长子串，实现线性时间复杂度且不使用max函数

原代码存在的问题 #

• 逻辑错误1：遇到重复字符时直接清空当前子串，会漏掉重复字符之后的有效子串（例如输入abca，正确无重复子串应为bca长度3，原代码会得到a长度1，结果错误）
• 逻辑错误2：如果最长无重复子串出现在字符串末尾，循环结束后不会把当前word加入evid列表，调用max时会抛出空序列错误
• 时间复杂度不符合线性要求：判断字符是否在当前子串if i not in word的时间复杂度是O(k)（k为当前子串长度），整体最坏复杂度为O(n²)，且额外存储所有历史子串会占用不必要的空间
• 用到了内置max函数，不符合要求

调整后符合要求的代码 #

class Solution:
    def lengthOfLongestSubstring(self, sentence):
        char_last_idx = {}  # 存储每个字符最后一次出现的索引
        left = 0  # 滑动窗口左边界
        max_len = 0  # 手动维护最大值，不使用max函数
        for right, char in enumerate(sentence):
            # 若当前字符在当前窗口内出现过，调整左边界到重复位置的下一位
            if char in char_last_idx and char_last_idx[char] >= left:
                left = char_last_idx[char] + 1
            # 更新当前字符的最后出现索引
            char_last_idx[char] = right
            # 计算当前窗口长度，手动更新最大值
            current_len = right - left + 1
            if current_len > max_len:
                max_len = current_len
        return max_len

print(Solution().lengthOfLongestSubstring('abrkaabcdefghijjxxx'))

代码说明 #

• 时间复杂度为O(n)：仅遍历字符串一次，哈希表的查询、插入操作均为O(1)，完全满足线性时间要求
• 未使用内置max函数：全程手动维护max_len变量，每次窗口调整后对比更新最大值
• 逻辑正确：采用滑动窗口方案动态调整边界，不会漏掉中间的有效无重复子串，测试用例输出结果为10，符合预期

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