Longest Substring Without Repeating Characters

1. Problem & Core Objective

The problem

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

A substring is contiguous. "pwke" is a subsequence of "pwwkew", not a substring.

Input:  s = "abcabcbb"      Output: 3      ("abc")
Input:  s = "bbbbb"         Output: 1      ("b")
Input:  s = "pwwkew"        Output: 3      ("wke" — not "pwke", which isn't contiguous)
Input:  s = ""              Output: 0

Constraints:

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

What the interviewer is actually testing

This is the canonical sliding window problem. If you can only rehearse one, rehearse this.

1. Do you recognize the longest-valid template? Expand always, shrink while invalid, record after validity is restored.
2. Can you state why it's O(n) despite a while nested inside a for?
3. Do you handle the stale-index trap? The map-based version breaks subtly if you don't check that a remembered index is still inside the window.
4. Do you catch "substring, not subsequence"? The "pwwkew" example is in the problem statement precisely to test whether you read it.

2. First-Principles Thought Process

Step 1 — Constraints

n up to 5 × 10^4.

• O(n³) (every substring × validity check) → hopeless.
• O(n²) → 2.5 × 10^9. Too slow.
• O(n) → the target.

Note the character set is not restricted to lowercase — letters, digits, symbols and spaces. So int[26] is out; you need int[128] for ASCII or a HashMap/HashSet for generality.

Step 2 — Brute force and its waste

For every start, extend until a repeat appears:

for (int i = 0; i < n; i++) {
    Set<Character> seen = new HashSet<>();
    for (int j = i; j < n && seen.add(s.charAt(j)); j++) best = Math.max(best, j - i + 1);
}

O(n²). The waste: when the window starting at i fails at position j, we throw away everything and restart at i + 1 — re-scanning almost the same characters.

Step 3 — The reframe

The failure at j is caused by one specific character repeating. Restarting from i + 1 is overkill: most of that window is still perfectly valid.

Instead of discarding the window, shrink it from the left just enough to remove the duplicate — then keep expanding.

That's the sliding window. The window [left, right] always contains distinct characters, and we grow it rightward, shrinking from the left only when forced.

Step 4 — Choose the summary

What must the window track to answer "is the incoming character already inside me?"

• A HashSet of the characters currently in the window — membership in O(1). Shrink one character at a time until the duplicate is evicted.
• A HashMap of character → its most recent index — lets left jump straight past the previous occurrence in one step.

Both are O(n). The set is easier to narrate; the map does fewer iterations.

Step 5 — The trap in the map version

The map remembers characters from before the current window too. Suppose s = "abba":

• At the second a (index 3), the map says a was last at index 0.
• But left has already moved past index 0 — the window is [2, 3] and contains no a.
• Jumping left back to 0 + 1 = 1 would move it backwards, growing the window to include the b at index 2 and index 1 — producing "bba", which has a repeat.

The fix: only react to a remembered index if it is still inside the window:

if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) left = lastSeen.get(c) + 1;

This is the detail that separates a working solution from one that passes the given examples and fails on "abba".

Step 6 — Why it's O(n)

left and right each only move forward and neither exceeds n. So between them they take at most 2n steps, regardless of how the inner while is written. Some iterations shrink several times; then several later iterations shrink none.

3. Solution Paths

Approach 1 — Brute force: check every substring

public int lengthOfLongestSubstring(String s) {
    int best = 0;
    for (int i = 0; i < s.length(); i++) {
        Set<Character> seen = new HashSet<>();
        for (int j = i; j < s.length(); j++) {
            if (!seen.add(s.charAt(j))) break;      // repeat found — this start is exhausted
            best = Math.max(best, j - i + 1);
        }
    }
    return best;
}

• Time: O(n²) — each start scans forward until a repeat.
• Space: O(min(n, alphabet)) for the set.

Counter-questions on this approach

⭐ "When the window starting at i fails, what do you actually throw away?"

Almost everything that was still valid. If "abcx...b" fails on the second b, restarting at i + 1 rebuilds "bcx..." character by character — even though the only real problem was the single b at the start. That's the observation that leads to shrinking instead of restarting.

"You use !seen.add(...) as the loop break. Why not seen.contains then add?"

add returns false when the element was already present, so test-and-insert is one hash computation instead of two. Same complexity, half the work — and it reads as a single intent rather than two steps.

Approach 2 — Sliding window with a HashSet

public int lengthOfLongestSubstring(String s) {
    Set<Character> window = new HashSet<>();
    int left = 0, best = 0;

    for (int right = 0; right < s.length(); right++) {
        while (window.contains(s.charAt(right))) {    // shrink until the duplicate is gone
            window.remove(s.charAt(left));
            left++;
        }
        window.add(s.charAt(right));
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Trace on "abcabcbb":

Answer: 3 ✓

• Time: O(n) — both pointers only advance.
• Space: O(min(n, alphabet)).

Counter-questions on this approach

⭐ "There's a while inside a for. Isn't that O(n²)?"

No. left and right each move only forward and neither exceeds n, so their combined movement is bounded by 2n. Some iterations shrink several times, but then several later iterations shrink none. It's aggregate accounting — you bound the total work over the whole run, not the worst case of one iteration.

⭐ "Why do you record best after the shrink loop rather than inside it?"

Because this is a longest-valid window. The window is only guaranteed valid once the shrink loop has finished restoring the invariant, so that's the only point where measuring it is meaningful. Shortest-valid problems are the mirror image — they record inside the loop, while the window is still valid. Getting that placement backwards is the most common structural bug in this section.

"Is right - left + 1 right, or off by one?"

It's inclusive on both ends, so the + 1 is required. Sanity check on a single character: left = right = 0 gives 0 - 0 + 1 = 1. Correct.

"Your set could hold the whole alphabet. Is the space really O(n)?"

It's O(min(n, k)) where k is the alphabet size. For ASCII that's bounded by 128, making it effectively O(1). I'd state the bound as O(min(n, k)) rather than a bare O(n), since the alphabet caps it.

Approach 3 — Sliding window with index jumping

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();   // char -> its most recent index
    int left = 0, best = 0;

    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);

        if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
            left = lastSeen.get(c) + 1;        // jump past the previous occurrence, in one step
        }
        lastSeen.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Trace on "abba" — the case that breaks the naive version:

Answer: 2 ✓ — at right = 3 the remembered index 0 is stale, outside the window, and correctly ignored.

• Time: O(n) — a single pass with no inner loop at all.
• Space: O(min(n, alphabet)).

Counter-questions on this approach

⭐ "What breaks if you drop the >= left check?"

"abba" returns 3 instead of 2. At right = 3, the map still remembers a at index 0 — from before the window. Without the guard, left jumps backwards to 1, and the window becomes "bba", which contains a repeat. left must never move backwards; the guard enforces that.

⭐ "Is this actually faster than the set version, given both are O(n)?"

Same complexity, fewer operations. The set version may execute the shrink loop many times for one arriving character; this jumps left in a single assignment. It's a constant-factor win. I'd write the set version first because it narrates more clearly, then offer this as the refinement.

"Why store the index rather than just membership?"

Because the index is what lets me jump. A set can only answer "is it present", which forces shrinking one character at a time until the duplicate happens to be evicted.

"Could you use an int[128] instead of the map?"

Yes, and it's faster — the constraints say English letters, digits, symbols and spaces, all ASCII. Initialize to -1 for "never seen". I'd switch to that if asked to optimize, and note it stops working the moment Unicode enters.

Comparison

4. Why the Optimal Wins

Against brute force. When a window fails, the brute force discards it entirely and rebuilds from the next index — re-reading characters it had already validated. The window shrinks by exactly as much as necessary and keeps the rest. That's the difference between O(n²) and O(n), and it's the core idea of the whole section.

Set version vs index-jump version. Identical complexity. The set shrinks one character at a time; the map jumps. The map is faster but carries the stale-index hazard, which is a real correctness risk under time pressure. Either is a good answer — what matters is being able to say why you chose one.

Why O(n) is the floor. Every character must be examined; an adversary can place the boundary of the longest substring anywhere you don't look. So O(n) is optimal.

The transferable structure:

Expand right unconditionally. Shrink left only while the window is invalid. Record after validity is restored.

That template solves this, Longest Repeating Character Replacement, and every other "longest valid window" problem. Learn it as a shape, not as code for one question.

5. Java Prerequisites

HashSet membership and the add return value

Set<Character> window = new HashSet<>();
window.contains(c);
window.add(c);          // returns false if already present
window.remove(c);

In the shrink loop, contains is the natural read. In the brute force, !add(...) collapses test-and-insert into one operation.

Map.getOrDefault vs containsKey + get

if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) { ... }   // two lookups

A single-lookup alternative:

Integer prev = lastSeen.get(c);
if (prev != null && prev >= left) left = prev + 1;

Or, avoiding the null check entirely by using a sentinel:

left = Math.max(left, lastSeen.getOrDefault(c, -1) + 1);

That one-liner is worth knowing. Math.max enforces "never move backwards" automatically, so the stale-index guard becomes structural rather than a separate if. If the character was never seen, -1 + 1 = 0 leaves left unchanged.

Boxed Integer comparison

lastSeen.get(c) >= left

Safe, because >= on a boxed Integer and an int auto-unboxes and compares numerically. The trap is ==, which compares references above the cache range of −128..127. See 03.

Window length

right - left + 1

Inclusive on both ends. Verify on a single character: 0 - 0 + 1 = 1. The + 1 is dropped constantly.

charAt vs toCharArray

s.charAt(i);          // O(1), no allocation — right for index-driven access
s.toCharArray();      // O(n) copy — right for one sequential pass

Both pointers index independently here, so charAt is correct.

Empty input

"".length() == 0     // the for loop never runs; best stays 0

Handled with no special case — worth confirming aloud rather than adding a defensive check.

6. Interview Communication Guide

Clarifying questions

1. "Substring or subsequence — does it need to be contiguous?" — substring. The "pwwkew" → "wke" example exists to test this.
2. "What character set? Just lowercase, or full ASCII, or Unicode?" — decides between int[26], int[128], and a HashMap.
3. "Do I return the length or the substring itself?" — the length; returning the substring means also tracking the start index.
4. "Is the comparison case-sensitive?" — 'a' and 'A' are different characters here.
5. "Can the string be empty?" — yes, and the answer is 0.

The pitch

"I need the longest contiguous run with no repeated character.

Brute force checks every starting position and extends until a repeat — O(n²). The waste is that when a window fails, it throws away the whole thing and restarts one position later, even though most of that window was still valid.

Instead I'll slide a window. I expand right one character at a time. If the incoming character is already inside the window, I shrink from the left until it isn't, then record the length. The window always holds distinct characters by invariant.

That's O(n) — both pointers only move forward, so together they take at most 2n steps, even though there's a while inside the for.

A refinement: instead of shrinking one character at a time, store each character's last index and jump left straight past the previous occurrence. The subtlety there is that the map remembers characters from before the window, so I have to check the remembered index is still >= left — otherwise left moves backwards and the window becomes invalid. \"abba\" is the case that catches it."

Edge cases to raise proactively

"abba" is the one to volunteer, and say why: it's the input where a remembered index has fallen outside the window, and reacting to it would move left backwards. "dvdf" is the second-best — it catches solutions that reset left to the wrong position.

7. Follow-Up Questions — Modified Constraints

The interviewer changes a constraint of the original problem and asks you to solve it again. ⭐ marks the most likely.

⭐ "What if at most k distinct characters were allowed, instead of zero repeats?" (LC 340)

The same longest-valid template with a different invariant. Keep a HashMap<Character,Integer> of counts in the window; shrink while map.size() > k, decrementing and removing on zero. O(n) time, O(k) space. This is the natural generalization — the original problem is the case where each character may appear at most once.

"What if you had to return the substring itself, not its length?"

Record left alongside best whenever the length improves, then s.substring(bestLeft, bestLeft + best) at the end. No complexity change.

"What if the input were Unicode rather than ASCII?"

The HashMap versions work unchanged. An int[128] would break. There's a further subtlety: Java char is 16 bits, so characters outside the Basic Multilingual Plane occupy two chars as a surrogate pair — iterating by char would treat half a character as a unit. The correct fix is s.codePoints().

"What if the string streams in and you can't index backwards?"

The set-based version needs to remove s.charAt(left), which requires random access. Buffer the window itself in a Deque<Character> so you can evict from the front without indexing the original string — O(k) memory in the window size rather than O(n).

"What if you wanted the longest substring where every character appears at least k times?" (LC 395)

The window invariant is no longer monotonic — adding a character can make a window valid or invalid unpredictably, so plain windowing breaks. The standard fix is divide-and-conquer: any character appearing fewer than k times cannot be in the answer, so split the string on it and recurse. Alternatively, run the window 26 times, once per fixed target number of distinct characters, which restores monotonicity. Worth flagging that the naive window fails here — recognizing when the technique doesn't apply is as valuable as applying it.

"What if you needed the longest substring with no repeats across a stream of queries on different ranges?"

A single window no longer suffices, since each query has its own bounds. You'd precompute, for each index, the furthest left a valid window can start — then answer range queries with a sparse table or segment tree in O(log n) per query after O(n log n) preprocessing.