Longest Substring Without Repeating Characters

What the problem is really asking

We need the longest continuous part of the string that contains no repeated character.

That means as soon as a duplicate appears, the current window becomes invalid.

Intuition

This is a classic sliding-window problem.

We grow the window from the right, and whenever the window becomes invalid, we shrink it from the left until it becomes valid again.

Brute-force idea

The slow method is to try every starting point and keep extending until a duplicate appears.

That can take O(n^2) time.

Optimized approach

Maintain:

• left pointer
• right pointer
• a map of character counts inside the current window

For each new character:

1. add it into the window
2. if it causes a duplicate, move left forward
3. keep shrinking until the duplicate disappears
4. update the best length

Each character enters and leaves the window at most once.

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0;
        int best = 0;

        for (int right = 0; right < s.length(); right++) {
            char current = s.charAt(right);
            window.put(current, window.getOrDefault(current, 0) + 1);

            while (window.get(current) > 1) {
                char leftChar = s.charAt(left++);
                window.put(leftChar, window.get(leftChar) - 1);
            }

            best = Math.max(best, right - left + 1);
        }

        return best;
    }
}

Dry run

Take s = "abcabcbb".

• window "a" -> best 1
• window "ab" -> best 2
• window "abc" -> best 3
• next char is "a" again, so the window is invalid
• move left until only one "a" remains

The best valid length stays 3.

Common mistakes

1. Resetting the whole window when a duplicate appears

You only need to shrink enough to remove the duplicate.

2. Forgetting to decrease counts when moving left

Then the map no longer matches the current window.

3. Thinking this is about subsequences

It is about substrings, so the characters must stay contiguous.

Complexity

Time Complexity: O(n)

Space Complexity: O(min(n, alphabet size))