MediumLeetCode #3Sliding Window

Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Constraints

0 <= s.length <= 5 * 10^4, s consists of English letters, digits, symbols and spaces

Examples

Input: s = "abcabcbb"

Output: 3

The answer is "abc", with the length of 3.

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