Leetcode 3. Longest Substring Without Repeating Characters

Problem

Given a string, determine the length of the longest contiguous substring that contains all unique characters (no character appears more than once within that substring).

You need to find the maximum length among all possible substrings where every character appears at most once.

Requirements

1. Return an integer representing the length of the longest valid substring
2. The substring must be contiguous (characters must appear consecutively in the original string)
3. Each character in the valid substring must be unique
4. If the input string is empty, return 0

Constraints

• 0 ≤ s.length ≤ 50,000
• The string consists of English letters, digits, symbols, and spaces
• Target time complexity: O(n) where n is the length of the string
• Target space complexity: O(min(m, n)) where m is the character set size

Examples

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: The longest substring without repeating characters is "abc", which has length 3.

Example 2:

Input: s = "bbbbb" Output: 1 Explanation: The longest substring is "b", with length 1.

Example 3:

Input: s = "pwwkew" Output: 3 Explanation: The longest substring is "wke", with length 3. Note that "pwke" is not valid because it's not a substring (the characters aren't consecutive).

Example 4:

Input: s = "" Output: 0 Explanation: An empty string has no characters.

Hint 1: Sliding Window Think about using a sliding window approach with two pointers. The right pointer expands the window by including new characters, while the left pointer contracts the window when you encounter a duplicate character.

Hint 2: Tracking Characters Use a hash map (dictionary) or set to keep track of characters you've seen in the current window. When you encounter a character that's already in your tracking structure, you need to adjust your window.

Hint 3: Window Adjustment When you find a duplicate character, move the left pointer to the position right after the previous occurrence of that character. This ensures all characters in the new window are unique.

Full Solution ` def lengthOfLongestSubstring(s: str) -> int: # Dictionary to store the most recent index of each character char_index = {} max_length = 0 left = 0 # Left pointer of the sliding window

# Iterate through the string with right pointer
for right in range(len(s)):
    current_char = s[right]
    
    # If character is already in window, move left pointer
    # to position after the previous occurrence
    if current_char in char_index and char_index[current_char] >= left:
        left = char_index[current_char] + 1
    
    # Update the character's most recent index
    char_index[current_char] = right
    
    # Calculate current window length and update maximum
    current_length = right - left + 1
    max_length = max(max_length, current_length)

return max_length

`

Approach:

This solution uses the sliding window technique with a hash map to efficiently track character positions.

Algorithm:

1. Initialize a dictionary to store the most recent index of each character

2. Use two pointers: left marks the start of the current window, and right iterates through the string

3. For each character at position right:

   • If the character exists in our window (appears in the dictionary at an index >= left), move left to the position right after the previous occurrence
   • Update the character's index in the dictionary
   • Calculate the current window length and update the maximum length if needed

4. Return the maximum length found

Time Complexity: O(n), where n is the length of the string. We iterate through the string once, and each character is visited at most twice (once by the right pointer, once when adjusting the left pointer).

Space Complexity: O(min(m, n)), where m is the size of the character set. In the worst case, we store all unique characters from the string in our dictionary.

Key Insights:

• The sliding window maintains the invariant that all characters within [left, right] are unique
• By storing indices rather than just existence, we can jump the left pointer directly to the correct position
• We only need to track characters currently in or recently exited from our window