🟨 Longest Substring Without Repeating Characters (#3)

🔗 Problem Link

• LeetCode - Longest Substring Without Repeating Characters
• NeetCode - Longest Substring Without Repeating Characters

📋 Problem Statement

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

💡 Examples

Example 1

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.

🔑 Key Insights & Approach

Core Observation: Use sliding window with a set to track unique characters. When duplicate found, shrink window from left.

Why Sliding Window + HashSet?

• O(n) time complexity
• Set provides O(1) lookup for duplicates
• Window expands right, shrinks left when duplicate found

Approaches:

1. Brute force all substrings: O(n³)
2. Sliding window with set: O(n) - optimal
3. Sliding window with hashmap (index tracking): O(n) - optimized

Pattern: "Sliding Window - Flexible Size" pattern for substring problems.

🐍 Solution: Python

Approach 1: Sliding Window with Set

Time Complexity: O(n) | Space Complexity: O(min(n, m)) where m is charset size

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_set = set()
        left = 0
        max_length = 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

            # Add current character
            char_set.add(s[right])

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

        return max_length

Approach 2: Optimized with HashMap (Index Tracking)

Time Complexity: O(n) | Space Complexity: O(min(n, m))

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_index = {}  # character -> last seen index
        left = 0
        max_length = 0

        for right, char in enumerate(s):
            # If character seen and in current window
            if char in char_index and char_index[char] >= left:
                left = char_index[char] + 1

            # Update character's last seen index
            char_index[char] = right

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

        return max_length

🔵 Solution: Golang

Approach: Sliding Window with Map

Time Complexity: O(n) | Space Complexity: O(min(n, m))

func lengthOfLongestSubstring(s string) int {
    charIndex := make(map[byte]int)
    left := 0
    maxLength := 0

    for right := 0; right < len(s); right++ {
        char := s[right]

        // If character seen in current window
        if lastIdx, exists := charIndex[char]; exists && lastIdx >= left {
            left = lastIdx + 1
        }

        charIndex[char] = right
        length := right - left + 1

        if length > maxLength {
            maxLength = length
        }
    }

    return maxLength
}

📚 References

• NeetCode - Longest Substring Without Repeating Characters