Editorial: Longest Substring Without Repeating Characters

1 Intuition

Use the sliding window technique with a hash map to track character positions. Expand the window by moving the right pointer, and shrink from the left when we encounter a duplicate character. This gives us O(n) time complexity.

2 Approach

1. Use a hash map to store character positions 2. Use left and right pointers for the sliding window 3. Expand right pointer and add characters: - If character already in map and within window, move left pointer - Update character position in map - Track maximum window size

3 Complexity Analysis

**Time Complexity:** O(n) - each character visited at most twice **Space Complexity:** O(min(m,n)) - hash map stores unique characters m = charset size, n = string length

4 Solution Code

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

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> char_map;
    int left = 0, max_length = 0;
    for (int right = 0; right < s.length(); right++) {
        if (char_map.count(s[right]) && char_map[s[right]] >= left) {
            left = char_map[s[right]] + 1;
        }
        char_map[s[right]] = right;
        max_length = max(max_length, right - left + 1);
    }
    return max_length;
}

5 Code Walkthrough

For s = "abcabcbb": - [a]bcabcbb: window="a", max=1 - [ab]cabcbb: window="ab", max=2 - [abc]abcbb: window="abc", max=3 - a[bca]bcbb: repeat 'a', move left, window="bca", max=3 - ab[cab]cbb: repeat 'a', move left, window="cab", max=3 - Continue... max=3