Python编写的最长无重复字符子串长度求解代码异常问题：小字符串正常运行，大字符串结果失效

Let's break down the critical issues in your current code that cause incorrect results—especially with large strings—and walk through how to fix them:

1. Incorrectly resetting the current substring on duplicates #

Your code clears the entire seq variable whenever it hits a duplicate character, which is a mistake. For example, take the input "dvdf":

• When you reach the second d, your code empties seq, losing the "v" that could form the longer valid substring "vdf" (length 3). Instead of wiping everything, you should only truncate seq to the part after the first occurrence of the duplicate character.

2. Failing to check the final substring after the loop ends #

If the longest substring sits at the end of the input (like "abcde" where there are no duplicates), your loop never triggers the else block to update result. This leaves result stuck at 0, returning an entirely wrong value.

Fix 1: Optimize your original code (simple, intuitive improvement) #

This fix adjusts how you handle duplicates and ensures we update the result every iteration, not just when a duplicate is found:

def lengthOfLongestSubstring(s):
    seq = ''
    result = 0
    for char in s:
        if char in seq:
            # Truncate seq to keep only the part after the duplicate character
            duplicate_idx = seq.index(char)
            seq = seq[duplicate_idx + 1:] + char
        else:
            seq += char
        # Update result with the current longest length every time
        if len(seq) > result:
            result = len(seq)
    return result

Key changes:

• Instead of clearing seq on duplicates, we cut off the segment before (and including) the duplicate, then append the current character.
• We check and update result in every iteration, so we don't miss the final valid substring at the end of the input.

Fix 2: Sliding Window with Hash Map (O(n) time complexity, ideal for large strings) #

Your original code has an O(n²) time complexity because checking char in seq is an O(n) operation for each character. For very large strings, this can be slow. The sliding window approach uses a hash map to track character positions, bringing the time complexity down to O(n):

def lengthOfLongestSubstring(s):
    char_last_index = {}
    left = 0
    max_length = 0
    
    for right, char in enumerate(s):
        # If the character is in the current window, move left pointer forward
        if char in char_last_index and char_last_index[char] >= left:
            left = char_last_index[char] + 1
        # Update the last seen index of the current character
        char_last_index[char] = right
        # Calculate current window length and update max_length
        current_length = right - left + 1
        if current_length > max_length:
            max_length = current_length
    
    return max_length

How this works:

• Two pointers (left and right) define the current window of non-repeating characters.
• The hash map char_last_index stores the most recent index of each character we've seen.
• When we hit a duplicate that's inside the current window, we move the left pointer to the right of the duplicate's last position to keep the window valid.
• We calculate the window length in each iteration and track the maximum length found.

Testing both fixes with your examples:

• For 'abrkaabcdefghijjxxx', both return 10 (correct, as "abcdefghij" is the longest valid substring).
• For your large test string, the sliding window approach will correctly identify the longest non-repeating substring (like "azertyuiop" which has length 10) instead of returning 6.

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