Problem Statement

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

Sliding Window Approach

The sliding window technique maintains a window defined by left and right pointers. As the right pointer expands the window, we track character frequencies. If a duplicate is found, the left pointer contracts the window until all characters are unique again.

Algorithm Implementation

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_freq = {}
        max_length = 0
        window_start = 0
        
        for window_end in range(len(s)):
            right_char = s[window_end]
            char_freq[right_char] = char_freq.get(right_char, 0) + 1
            
            # Shrink the window from the left if duplicates exist
            while char_freq[right_char] > 1:
                left_char = s[window_start]
                char_freq[left_char] -= 1
                if char_freq[left_char] == 0:
                    del char_freq[left_char]
                window_start += 1
                
            # Update the maximum length found so far
            max_length = max(max_length, window_end - window_start + 1)
            
        return max_length

General Sliding Window Template

For problems involving contiguous subarrays or substrings, a standard framework can be applied:

def sliding_window_framework(input_data):
    window_state = {}  # e.g., frequency map
    result = 0
    
    left = 0
    for right in range(len(input_data)):
        # Expand the window by including the element at 'right'
        # Update window_state accordingly
        
        # Contract the window from the 'left' if the window becomes invalid
        while is_invalid(window_state):
            # Remove the element at 'left' from window_state
            left += 1
            
        # Update the result if the current window is valid and optimal
        result = max(result, right - left + 1)
        
    return result

Related Practice Problems

• Maximum Average Subarray I
• Longest Substring with At Most Two Distinct Characters
• Minimum Size Subarray Sum
• Maximum Erasure Value
• Find All Anagrams in a String
• Permutation in String
• Max Consecutive Ones II
• Max Consecutive Ones III
• Get Equal Substrings Within Budget
• Grumpy Bookstore Owner
• Maximum Points You Can Obtain from Cards
• Minimum Swaps to Group All 1's Together