Free lesson · DSA Mastery - Interview Prep, End to End

Longest Substring Without Repeating Characters

Medium8 min readdsasliding-window

Longest Substring Without Repeating Characters

This is the most famous sliding-window problem, and the one that establishes the dynamic-window template for the entire rest of the module. Unlike fixed-size windows, here the window grows and shrinks based on a condition: it must contain no repeated character. We climb three approaches: brute force (check every substring for uniqueness, O(n³) or O(n²)), a set-based expanding window (O(n) but with redundant single-step shrinking), and the optimal last-seen-index jump that moves left directly past the previous occurrence (O(n)).

Internalize the template here - expand right, restore validity by moving left, update the answer - because the next fourteen problems are variations on it.

The Problem

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

Example 1:

Input:  s = "abcabcbb"
Output: 3

Explanation: The answer is "abc", with length 3.

Example 2:

Input:  s = "bbbbb"
Output: 1

Explanation: The answer is "b", with length 1.

Example 3:

Input:  s = "pwwkew"
Output: 3

Explanation: The answer is "wke", with length 3. Note "pwke" is a subsequence, not a substring.

Constraints:

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

Approaches Overview

#	Approach	Time	Space	Verdict
1	Brute force (check all substrings)	O(n²)	O(min(n,Σ))	Baseline; too slow
2	Expanding window + set (shrink one step)	O(n)	O(min(n,Σ))	Linear; simple
3	Window + last-seen-index jump	O(n)	O(min(n,Σ))	Optimal (single pass)

Both window approaches are O(n); the third is a refinement that jumps left in one move instead of shrinking character by character. Σ is the alphabet size.

Approach 1: Brute Force

The Idea

Consider every starting index; extend until a repeat appears, tracking the longest unique run. Using a set to test "all unique so far" makes each start O(n), so O(n²) overall.

Logic Flowchart

graph TD
    A["best = 0"] --> B["For start i = 0 to n-1"]
    B --> C["seen = {}; j = i"]
    C --> D{"j < n AND s[j] not in seen?"}
    D -->|Yes| E["add s[j]; j++"]
    E --> D
    D -->|No| F["best = max(best, j - i)"]
    F --> G{"More i?"}
    G -->|Yes| B
    G -->|No| H["Return best"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the brute-force approach. For each start index, we extend as far as possible while characters stay unique, using a set, and record the run length. Restarting the scan at every index gives quadratic time.

Code

public static int lengthOfLongestSubstringBrute(String s) {
    int best = 0, n = s.length();
    for (int i = 0; i < n; i++) {
        Set<Character> seen = new HashSet<>();
        int j = i;
        while (j < n && !seen.contains(s.charAt(j))) {
            seen.add(s.charAt(j));
            j++;
        }
        best = Math.max(best, j - i);
    }
    return best;
}

This Java code extends a unique run from each start index using a set, recording the longest. Restarting from every index makes it quadratic.

Complexity

Time: O(n²). Space: O(min(n, Σ)).

When start i fails at some j, brute force discards everything and restarts at i+1 - even though much of [i, j) was already known unique. A window keeps that progress.

Approach 2: Expanding Window + Set - Optimal (Linear)

Interactive animation: The window grows on the right and shrinks from the left while the new character repeats - green holds the rule, red breaks it.

The Idea

Maintain a window [left, right] and a set of its characters. Expand right; if s[right] is already in the set, shrink from left (removing characters) until the duplicate is gone, then add s[right]. Track the max window size. Each character is added once and removed once, so it's O(n).

Logic Flowchart

graph TD
    A["set = {}, left = 0, best = 0"] --> B["For right = 0 to n-1"]
    B --> C{"s[right] in set?"}
    C -->|Yes| D["remove s[left]; left++"]
    D --> C
    C -->|No| E["add s[right]"]
    E --> F["best = max(best, right - left + 1)"]
    F --> G{"More?"}
    G -->|Yes| B
    G -->|No| H["Return best"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the expanding-window approach. We grow the window on the right; if the entering character duplicates one inside, we shrink from the left until the duplicate leaves, then add it. We track the largest window. Each character enters and leaves once.

Code

public static int lengthOfLongestSubstringSet(String s) {
    Set<Character> set = new HashSet<>();
    int left = 0, best = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        while (set.contains(c)) {
            set.remove(s.charAt(left));
            left++;
        }
        set.add(c);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

This Java code maintains a set of the window's characters. When the entering character is already present, it removes characters from the left until the duplicate is gone, then adds the new character and updates the best length. Linear time overall.

Complexity

Time: O(n). Space: O(min(n, Σ)).

The only inefficiency: when a duplicate appears, we shrink one character at a time. Knowing where the previous occurrence was lets us jump left in a single move.

Approach 3: Last-Seen-Index Jump - Optimal (Single Pass)

The Idea

Store a map from character → its last seen index. When s[right] was seen at index p and p >= left (inside the current window), jump left directly to p + 1 - skipping all the one-step removals. Update the character's last index to right, and track the max window size. One pass, no inner loop.

Logic Flowchart

graph TD
    A["lastSeen = {}, left = 0, best = 0"] --> B["For right = 0 to n-1"]
    B --> C{"s[right] in lastSeen<br/>AND lastSeen[s[right]] >= left?"}
    C -->|Yes| D["left = lastSeen[s[right]] + 1"]
    C -->|No| E["left unchanged"]
    D --> F["lastSeen[s[right]] = right"]
    E --> F
    F --> G["best = max(best, right - left + 1)"]
    G --> H{"More?"}
    H -->|Yes| B
    H -->|No| I["Return best"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the optimal last-seen-index approach. We track each character's most recent index. When the entering character was last seen inside the window, we jump the left boundary just past that occurrence in one move, then update the character's index and the best length. A single pass with no inner loop.

Code

public static int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> lastSeen = new HashMap<>();
    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 previous occurrence
        }
        lastSeen.put(c, right);
        best = Math.max(best, right - left + 1);
    }
    return best;
}

// Usage:
// lengthOfLongestSubstring("abcabcbb") -> 3
// lengthOfLongestSubstring("bbbbb")    -> 1
// lengthOfLongestSubstring("pwwkew")   -> 3

This Java code records each character's most recent index. When the entering character was last seen inside the current window, the left boundary jumps just past that index in one step. It updates the character's index and the best length each iteration, in a single pass.

Step-by-Step Walkthrough

Interactive animation: Step through the brute force, the set window and the last-seen jump on each example and on abba.

A frame-by-frame trace on s = "pwwkew". Each frame shows right, the window, any jump, and the best length:

graph LR
    F0["right=0 'p'<br/>window 'p'<br/>best=1"]
    F1["right=1 'w'<br/>window 'pw'<br/>best=2"]
    F2["right=2 'w'<br/>seen@1>=left<br/>left jumps to 2<br/>window 'w', best=2"]
    F3["right=3 'k'<br/>window 'wk'<br/>best=2"]
    F4["right=4 'e'<br/>window 'wke'<br/>best=3"]
    F5["right=5 'w'<br/>seen@2>=left<br/>left jumps to 3<br/>window 'kew', best=3"]
    F0 --> F1 --> F2 --> F3 --> F4 --> F5

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F2 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F3 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F5 fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This walkthrough traces p w w k e w. The window grows to p w with length two. The second w was seen at index one, so left jumps to two. The window then grows w k e to length three. The final w was last seen at index two, so left jumps to three, giving window k e w, also length three. The answer is three.

Result: 3.

Complexity

Time: O(n) - single pass, O(1) per step. Space: O(min(n, Σ)) - the last-seen map.

Complexity Comparison

Approach	Time	Space	Key Idea	When to Use
Brute force	O(n²)	O(min(n,Σ))	Restart scan per start	Baseline only
Expanding window + set	O(n)	O(min(n,Σ))	Shrink one char at a time	Clear and correct
Last-seen-index jump	O(n)	O(min(n,Σ))	Jump `left` past prior occurrence	Optimal single pass

Both windows are linear; the jump version avoids the inner shrink loop entirely. The guard lastSeen.get(c) >= left is essential - a previous occurrence outside the current window must not pull left backward.

Interactive animation: Every possible window as a grid: the sliding window draws one path that only steps right or down, at most 2n steps.

Variations & Follow-ups

What if you needed the substring itself, not its length?

Record the window's start whenever best updates; slice s[bestStart, bestStart + best].

What if at most one repeat were allowed?

That generalizes to "at most k distinct" or "longest with at most one duplicate" - handled by the at-most-k template (12.18).

Why does the `>= left` guard matter?

Without it, a character last seen before left would wrongly jump left backward, growing the window to include a duplicate. The guard ensures we only jump when the prior occurrence is still inside the window.

Interactive animation: On abba the last a was seen at 0, before left = 2, so the guard ignores it and left never moves backward.

Fixed array instead of a hash map?

If the alphabet is small/known (e.g. ASCII), a int[128] of last-seen indices (initialized to -1) is faster than a hash map and equally simple.

What about edge cases?

Empty string: Returns 0.
All identical: Returns 1.
All distinct: Returns n (window never shrinks).
Single character: Returns 1.

Common Interview Pitfalls

Letting left move backward. Always left = max(left, lastSeen.get(c) + 1) or guard with >= left.
Updating the answer before restoring validity. Compute right - left + 1 after the jump.
Confusing substring with subsequence. Substrings are contiguous; "pwke" in Example 3 is a subsequence and doesn't count.
Forgetting to update the last-seen index every step. It must be set for every character, matched or not.

Why This Problem Matters

Longest Substring Without Repeating Characters is the archetype of the dynamic window and the source of the template that drives the rest of the module: expand right, restore validity (shrink left), update the answer. The last-seen-index optimization also previews a recurring idea - storing positional information in the map to jump rather than crawl.

The next topic, Longest Repeating Character Replacement, keeps the "longest valid window" shape but introduces a subtler validity condition: a window is valid if it can be made uniform by replacing at most k characters - which means tracking the most frequent character in the window.

Back to DSA Mastery - Interview Prep, End to End

Longest Substring Without Repeating Characters

Longest Substring Without Repeating Characters

The Problem

Approaches Overview

Approach 1: Brute Force

The Idea

Logic Flowchart

Code

Complexity

Approach 2: Expanding Window + Set - Optimal (Linear)

The Idea

Logic Flowchart

Code

Complexity

Approach 3: Last-Seen-Index Jump - Optimal (Single Pass)

The Idea

Logic Flowchart

Code

Step-by-Step Walkthrough

Complexity

Complexity Comparison

Variations & Follow-ups

What if you needed the substring itself, not its length?

What if at most one repeat were allowed?

Why does the >= left guard matter?

Fixed array instead of a hash map?

What about edge cases?

Common Interview Pitfalls

Why This Problem Matters

Why does the `>= left` guard matter?