To solve this problem, we need to find the length of the longest substring without repeating characters in a given string. The optimal approach to this problem is using the sliding window technique, which efficiently tracks the current substring and adjusts its boundaries to avoid duplicates.

Approach

The sliding window technique uses two pointers (left and right) to represent the current window of the substring we are checking. We also use a set to keep track of characters in the current window to quickly detect duplicates:

1. Initialization: Start with left pointer at 0, max_len to store the length of the longest substring found, and an empty set char_set to track characters in the current window.
2. Expand the window: Iterate over the string with the right pointer. For each character:
   • If the character is already in char_set, move the left pointer to the right, removing characters from char_set until the duplicate character is removed.
   • Add the current character to char_set.
   • Update max_len if the current window size (from left to right) is larger than the current max_len.
3. Return Result: The max_len will be the length of the longest substring without repeating characters.

Solution Code

def length_of_longest_substring(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        current_len = right - left + 1
        if current_len > max_len:
            max_len = current_len

    return max_len

# Example usage and test cases
if __name__ == "__main__":
    test_cases = [
        ("abcabcbb", 3),
        ("bbbbb", 1),
        ("pwwkew", 3),
        ("", 0),
        ("a", 1),
        ("au", 2)
    ]

    for s, expected in test_cases:
        result = length_of_longest_substring(s)
        assert result == expected, f"Test case failed: Input {s} → Expected {expected}, Got {result}"

    print("All test cases passed successfully!")

Explanation

• Efficiency: The algorithm runs in O(n) time complexity, where n is the length of the string. Each character is added to and removed from the set at most once, so the total operations are linear.
• Space Complexity: The space complexity is O(k), where k is the number of unique characters in the string. For example, if the string consists of all unique characters, k = n, but for a fixed character set (like lowercase letters), k is constant (O(1)).

This approach efficiently handles all edge cases, including empty strings, strings with all unique characters, and strings with repeated characters. The test cases confirm the correctness of the solution.

作者声明:本文包含人工智能生成内容。