leetcode-3 Longest Substring Without Repeating Characters

# Given a string s, find the length of the longest substring without repeating characters.
#
# Example 1:
# Input: s = "abcabcbb"
# Output: 3
# Explanation: The answer is "abc", with length 3.
#
# Example 2:
# Input: s = "bbbbb"
# Output: 1
# Explanation: The answer is "b", with length 1.
#
# Example 3:
# Input: s = "pwwkew"
# Output: 3
# Explanation: The answer is "wke", with length 3.
#
# Constraints:
# 0 <= s.length <= 5 * 10^4
# s consists of English letters, digits, symbols and spaces.

class Solution:
    # Approach 1: Sliding Window with Hash Map
    def lengthOfLongestSubstring(self, s: str) -> int:
        # Map character to its latest index
        char_index = {}
        max_length = 0
        left = 0

        for right in range(len(s)):
            char = s[right]

            # If char is in window, move left pointer
            if char in char_index and char_index[char] >= left:
                left = char_index[char] + 1

            # Update char's latest index
            char_index[char] = right

            # Update max length
            max_length = max(max_length, right - left + 1)

        return max_length

    # Approach 2: Sliding Window with Set
    def lengthOfLongestSubstring2(self, s: str) -> int:
        char_set = set()
        max_length = 0
        left = 0

        for right in range(len(s)):
            # Remove characters until no duplicate
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1

            char_set.add(s[right])
            max_length = max(max_length, right - left + 1)

        return max_length

# Time Complexity: O(n) - each character visited at most twice
# Space Complexity: O(min(n, m)) where m is charset size
#
# Sliding Window Pattern:
# 1. Expand window by moving right pointer
# 2. When constraint violated (duplicate found), shrink from left
# 3. Track maximum valid window size
#
# Key Insight: When duplicate found, we can jump left pointer
# directly to after the previous occurrence (using hash map)
# instead of moving it one by one