Longest Substring Without Repeating Characters

MediumSliding Window · Dynamic Size🧩 Sliding Window LeetCode #3 ↗Updated Oct 30, 2026

Problem

Given a string s, return the length of the longest contiguous piece of it in which no character appears twice. A subsequence (skipping characters) does not count — the characters must be adjacent.

Inputs = "abcabcbb"Output3 ("abc")

Inputs = "bbbbb"Output1 ("b")

Inputs = "pwwkew"Output3 ("wke")

0 ≤ n ≤ 5·10⁴ · s holds English letters, digits, symbols and spaces (ASCII)

Try it yourself

Java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Keep a window [left..right] with no duplicates. When s[right] was already seen inside the window, jump left just past its previous index — every start before that would contain the same repeat.

PatternSliding Window

Instinct Longest, shortest or count of contiguous subarrays/substrings meeting a rule? Grow a window on the right, shrink it on the left, never step back.

Memory hack Move like a caterpillar - the head stretches forward to grab, the tail pulls up only when the body breaks the rule.

Open the Sliding Window guide →

Approaches

Brute ForceCheck Every Substring

Time O(n³)Space O(min(n, k))

Try every pair (i, j) and test whether s[i..j] is duplicate-free with a fresh HashSet. Keep the longest length that passes. (k = alphabet size.)

Java

public int lengthOfLongestSubstring(String s) {
    int n = s.length(), maxLength = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (isUnique(s, i, j)) maxLength = Math.max(maxLength, j - i + 1);
        }
    }
    return maxLength;
}

private boolean isUnique(String s, int start, int end) {
    Set<Character> chars = new HashSet<>();
    for (int k = start; k <= end; k++) {
        if (!chars.add(s.charAt(k))) return false; // already present
    }
    return true;
}

Obviously correct, but re-scans each of the O(n²) substrings from scratch.

BetterSliding Window + HashSet

Time O(n)Space O(min(n, k))

The set holds exactly the characters of the window [i, j). If s[j] is new, grow right; otherwise shrink from the left one step at a time until the duplicate is evicted. Each pointer moves at most n times.

Java

public int lengthOfLongestSubstring(String s) {
    int n = s.length(), maxLength = 0, i = 0, j = 0;
    Set<Character> window = new HashSet<>();
    while (j < n) {
        if (!window.contains(s.charAt(j))) {
            window.add(s.charAt(j++));
            maxLength = Math.max(maxLength, j - i);
        } else {
            window.remove(s.charAt(i++)); // shrink until duplicate leaves
        }
    }
    return maxLength;
}

Linear, but may take up to 2n steps because i creeps one char at a time.

OptimalSliding Window + Last-Index Table

Time O(n)Space O(k)

Store, per character, lastIndex + 1 in an int[128]. On reading s[right], set left = max(left, last[c]) — the max ignores stale entries that lie before the current window. One pass, no inner loop.

Java

public int lengthOfLongestSubstring(String s) {
    int[] last = new int[128]; // last index + 1 of each char (0 = unseen)
    int best = 0;
    for (int left = 0, right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        left = Math.max(left, last[c]); // jump past the previous copy
        last[c] = right + 1;
        best = Math.max(best, right - left + 1);
    }
    return best;
}

Dry runs = "pwwkew"

l leftr right changed

r=0
p
l r
w

w

k

e

w

len 1, best=1
r=1
p
l
w
r
w

k

e

w

len 2, best=2
r=2
p

w

w
l r
k

e

w

w seen @1 → left=2
r=3
p

w

w
l
k
r
e

w

len 2
r=4
p

w

w
l
k

e
r
w

len 3, best=3
r=5
p

w

w

k
l
e

w
r
w seen @2 → left=3 ✔

Single pass of n steps; the 128-slot table is effectively O(1) space.

Pro tip

Try "abba": without the max, the second a would drag left backwards to 1.

At a glance

Level	Approach	Time	Space
Brute Force	Check Every Substring	`O(n³)`	`O(min(n, k))`
Better	Sliding Window + HashSet	`O(n)`	`O(min(n, k))`
Optimal	Sliding Window + Last-Index Table	`O(n)`	`O(k)`

Common pitfalls

Setting left = last[c] without max — left moves backwards ("abba").
Off-by-one in window length: it is right - left + 1 for an inclusive window.
Using int[26] — input may contain digits, spaces and symbols.

Interview tips

Clarify the charset first; it decides array vs HashMap.
Explain why the set version is still O(n): each index enters and leaves once.
State the invariant: the window never contains a repeat.

Pattern

Variable-size sliding window → longest/shortest contiguous range satisfying a constraint that breaks monotonically.

My notes saved in this browser