[Medium] 3. Longest Substring Without Repeating Characters

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.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints

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

Solution: Sliding Window with Hash Map

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

Use a sliding window approach with a hash map to track character positions and efficiently update the window boundaries.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0
        hashmap = {}
        start = 0

        for end in range(len(s)):
            cur = s[end]

            if cur in hashmap and hashmap[cur] >= start:
                start = hashmap[cur] + 1

            hashmap[cur] = end
            max_len = max(max_len, end - start + 1)

        return max_len

How the Algorithm Works

Step-by-Step Example: s = "abcabcbb"

Step end cur hashmap start window max_len
1 0 ‘a’ {‘a’: 0} 0 “a” 1
2 1 ‘b’ {‘a’: 0, ‘b’: 1} 0 “ab” 2
3 2 ‘c’ {‘a’: 0, ‘b’: 1, ‘c’: 2} 0 “abc” 3
4 3 ‘a’ {‘a’: 3, ‘b’: 1, ‘c’: 2} 1 “bca” 3
5 4 ‘b’ {‘a’: 3, ‘b’: 4, ‘c’: 2} 2 “cab” 3
6 5 ‘c’ {‘a’: 3, ‘b’: 4, ‘c’: 5} 3 “abc” 3
7 6 ‘b’ {‘a’: 3, ‘b’: 6, ‘c’: 5} 5 “cb” 3
8 7 ‘b’ {‘a’: 3, ‘b’: 7, ‘c’: 5} 7 “b” 3

Final Answer: 3

Visual Representation

String: "abcabcbb"
        01234567

Step 1-3: "abc" (length 3)
Step 4:   "bca" (length 3) 
Step 5:   "cab" (length 3)
Step 6:   "abc" (length 3)
Step 7:   "cb"  (length 2)
Step 8:   "b"   (length 1)

Maximum length: 3

Key Insights

  1. Sliding Window: Use two pointers (start and end) to maintain a valid window
  2. Hash Map Tracking: Store the last position of each character
  3. Efficient Updates: When a duplicate is found, move start to hashmap[cur] + 1
  4. Single Pass: Process each character exactly once

Algorithm Breakdown

1. Initialize Variables

max_len = 0
hashmap = {}  # Dictionary to store character positions

2. Expand Window

start = 0
for end in range(len(s)):
    cur = s[end]

3. Handle Duplicates

if cur in hashmap and hashmap[cur] >= start:
    start = hashmap[cur] + 1  # Move start past duplicate

4. Update and Track

hashmap[cur] = end  # Update character position
max_len = max(max_len, end - start + 1)  # Update max length

Alternative Approaches

Approach 1: Brute Force

# Check all possible substrings - O(n³)
for i in range(n):
    for j in range(i, n):
        if isUnique(s, i, j):
            max_len = max(max_len, j - i + 1)

Approach 2: Sliding Window with Set

# Use set to track characters in current window
window = set()
start = 0
for end in range(len(s)):
    while s[end] in window:
        window.remove(s[start])
        start += 1
        window.add(s[end])
        max_len = max(max_len, end - start + 1)

Complexity Analysis

Approach Time Complexity Space Complexity
Brute Force O(n³) O(min(m, n))
Sliding Window + Set O(n) O(min(m, n))
Sliding Window + Hash Map O(n) O(min(m, n))

Edge Cases

  1. Empty string: s = "" → 0
  2. Single character: s = "a" → 1
  3. All same characters: s = "aaaa" → 1
  4. No duplicates: s = "abcdef" → 6

Why This Solution is Optimal

  1. Single Pass: Each character is visited exactly once
  2. Efficient Lookup: Hash map provides O(1) character position lookup
  3. Smart Window Adjustment: Directly jumps to the correct position instead of sliding one by one
  4. Minimal Space: Only stores character positions, not the entire substring

Common Mistakes

  1. Not checking if duplicate is within current window
  2. Using start = end instead of start = hashmap[cur] + 1
  3. Forgetting to update max_len after each iteration
  4. Not handling edge cases like empty string