LeetCode Solutions Blog

Longest Substring Without Repeating Characters

Number: 3

Difficulty: Medium

Paid? No

Problem Description

Given a string s, determine the length of the longest substring that does not contain any repeating characters.

Key Insights

Use the sliding window technique to maintain a window of unique characters.
Use a hash table (or dictionary) to quickly check for duplicate characters and update window boundaries.
The window is expanded by moving a pointer (right) and contracted by moving another pointer (left) when duplicates are encountered.
Time complexity can be maintained at O(n) by ensuring each character is processed a limited number of times.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the input string. Space Complexity: O(min(n, m)), where m is the size of the character set (constant for fixed character sets).

Solution

The solution uses a sliding window technique with two pointers, left and right, to keep track of the current substring without repeating characters. A hash table (dictionary or map) is used to store the most recent index of each character encountered. As the right pointer moves forward, if a duplicate character is found within the current window, the left pointer is advanced to the position right after where the duplicate was last seen. This ensures that the window always contains unique characters. The maximum length is updated throughout the process.

Code Solutions

# Function to find the length of the longest substring without repeating characters
def length_of_longest_substring(s):
    # Dictionary to store the most recent index of each character
    char_index = {}
    # Initialize starting index of current window and max length
    left = 0
    max_length = 0
    
    # Iterate over the string with the right pointer
    for right, char in enumerate(s):
        # If char is in dictionary and its index is within the current window
        if char in char_index and char_index[char] >= left:
            # Move the left pointer to one position after the last occurrence of char
            left = char_index[char] + 1
        # Update the latest index of the char
        char_index[char] = right
        # Update max_length with the current window size if larger
        max_length = max(max_length, right - left + 1)
    
    return max_length

# Example usage:
# print(length_of_longest_substring("abcabcbb"))  # Expected output: 3