To solve this problem, we need to find the length of the longest substring without repeating characters. This is a classic problem that can be efficiently solved using the sliding window technique combined with a hash map to track character positions.

Approach

The sliding window technique involves maintaining a window (defined by two pointers, left and right) that represents the current substring we are examining. We use a hash map to store the last occurrence of each character within the current window. Here's the step-by-step approach:

1. Initialize:

   • A dictionary (char_map) to keep track of the last index of each character.
   • left pointer to the start of the window (initially 0).
   • max_length to store the length of the longest substring found (initially 0).

2. Iterate:

   • For each character at position right (from 0 to the end of the string):
     • If the character is already in char_map and its last occurrence is within the current window (i.e., char_map[char] >= left), move the left pointer to the right of the last occurrence of the character to avoid duplicates.
     • Update the char_map with the current character's index (right).
     • Calculate the length of the current window (right - left + 1) and update max_length if this length is greater than the current max_length.

3. Return: The max_length as the result.

Solution Code

def length_of_longest_substring(s: str) -> int:
    char_map = {}
    left = 0
    max_len = 0
    for right in range(len(s)):
        char = s[right]
        if char in char_map and char_map[char] >= left:
            left = char_map[char] + 1
        char_map[char] = right
        current_len = right - left + 1
        if current_len > max_len:
            max_len = current_len
    return max_len

Explanation

• Sliding Window: The window is adjusted dynamically as we encounter duplicate characters. This ensures we always consider the longest valid substring ending at the current position right.
• Hash Map: The hash map allows O(1) time complexity for checking the presence of a character and updating its last occurrence. This makes the overall time complexity of the solution O(n), where n is the length of the string, as each character is processed exactly once.
• Edge Cases: Handles empty strings (returns 0), single characters (returns 1), and all unique characters (returns the length of the string).

This approach efficiently finds the longest substring without repeating characters with optimal time and space complexity. The space complexity is O(min(m, n)), where m is the size of the character set (e.g., 26 for lowercase letters, 128 for ASCII), as the hash map can store at most m unique characters. However, in practice, it's O(n) in the worst case (all unique characters).

Example: For the input "abcabcbb", the longest substring without repeating characters is "abc" with length 3. The code correctly identifies this by adjusting the window whenever a duplicate is found.

This solution is both optimal and easy to understand, making it a standard approach for this problem.

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