yaohwang.com

Problem Overview

Given a string s, find the length of the longest substring without repeating characters. Digits are in normal order; we scan left-to-right.

Solution 1: Brute Force (Worst)

How It Works

Enumerate every starting index and extend until a duplicate appears, tracking seen characters in a set:

for i in range(n):
    seen = set()
    for j in range(i, n):
        if s[j] in seen:
            break
        seen.add(s[j])
        best = max(best, j - i + 1)

Complexity Analysis

• Time Complexity: O(n²) – nested loops: O(n) for start position, O(n) for end position
• Space Complexity: O(min(n, charset)) for the set

When to Use

• Simple to reason about but too slow for large n
• Good only as a baseline for understanding the problem

Solution 2: Sliding Window (Better)

How It Works

Maintain a window [start, i] and a map of last positions. When we see a duplicate of ch, move start to last_pos[ch] + 1. Update best length as we go:

last_pos = {}
start = 0
best = 0

for i, ch in enumerate(s):
    if ch in last_pos and last_pos[ch] >= start:
        start = last_pos[ch] + 1
    last_pos[ch] = i
    best = max(best, i - start + 1)

Detailed Step-by-Step Explanation

Core Idea: Instead of checking all substrings starting from each position (O(n²)), we maintain a sliding window [start, i] that represents the current valid substring without duplicates. The window expands to the right as we process characters, and contracts from the left when we encounter a duplicate.

Key Components:

1. last_pos: Dictionary mapping each character to its last seen position (index)
2. start: Left boundary of the current valid window
3. i: Right boundary (current position being processed)
4. best: Length of the longest valid substring found so far

Algorithm Flow:

For each character at position i:

1. Check for duplicate: If ch was seen before (ch in last_pos) AND its last position is within the current window (last_pos[ch] >= start), we have a duplicate.
2. Slide window: Move start to last_pos[ch] + 1 to exclude the previous occurrence of ch from the window.
3. Update position: Record the current position of ch in last_pos[ch] = i.
4. Update best: Calculate current window length i - start + 1 and update best if it’s longer.

Key Insight

Instead of checking all substrings starting from each position, we maintain a sliding window. When we encounter a duplicate character, we slide the window’s start position past the previous occurrence, avoiding redundant checks. This eliminates the need to restart from every position, reducing time complexity from O(n²) to O(n).

Complexity Analysis

• Time Complexity: O(n) – single pass through the string, each character visited exactly once
• Space Complexity: O(min(n, charset)) for the map – stores at most one entry per distinct character

When to Use

• Recommended for production code
• Handles arbitrary Unicode safely (dict grows with distinct chars)
• Optimal solution for this problem

Comparison

Takeaway

The sliding window approach is the optimal solution, reducing time complexity from O(n²) to O(n) by maintaining a dynamic window and tracking character positions. This demonstrates the power of the sliding window technique for substring problems.