MediumSliding Window

Longest Substring Without Repeating

Find longest substring without repeating

Solution Approach

Maintain a window of elements with a specific property. Expand window by moving right pointer, contract by moving left pointer when condition is violated. Use HashMap/Set to track elements in current window.

Implementation

def lengthOfLongestSubstring(s):
    char_map = {}
    max_length = 0
    left = 0
    for right in range(len(s)):
        if s[right] in char_map:
            left = max(left, char_map[s[right]] + 1)
        char_map[s[right]] = right
        max_length = max(max_length, right - left + 1)
    return max_length

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(min(m, n))

Key Learning Points

Maintain valid window with two pointersUse HashMap for character trackingExpand right, contract left when needed