Longest Substring Without Repeating Characters

Problem Statement

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

Example: Input: "abcabcbb" → Output: 3 ("abc")

Approach 1: Brute Force

Explanation: Generate all substrings, check if characters are unique.

Time Complexity: O(n³)

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

max_len = 0
for i = 0 to n-1:
    for j = i to n-1:
        if all chars in s[i..j] are unique:
            max_len = max(max_len, j-i+1)
return max_len

💡 Think: Test all substrings and keep the longest with all unique characters.

Approach 2: Sliding Window

Explanation: Use two pointers and a set to maintain unique characters in current window.

Time Complexity: O(n)

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

set = empty
left = 0, max_len = 0
for right = 0 to n-1:
    while s[right] in set:
        remove s[left] from set
        left++
    add s[right] to set
    max_len = max(max_len, right-left+1)
return max_len

💡 Think: Grow window with a set; shrink from left on repeats to maintain uniqueness.

Approach 3: Sliding Window with Hash Map (Optimal)

Explanation: Store last index of characters to skip duplicates efficiently.

Time Complexity: O(n)

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

map = empty
left = 0, max_len = 0
for right = 0 to n-1:
    if s[right] in map:
        left = max(map[s[right]]+1, left)
    map[s[right]] = right
    max_len = max(max_len, right-left+1)
return max_len

💡 Think: Jump left via last-seen index map to skip over repeated characters fast.

Solve on LeetCode