16.Longest Substring Without Repeating Characters

MediumBlind 75Sliding Window · 2/6

Problem

Given a string s, return the length of the longest substring that contains no repeated characters.

A substring is a contiguous block of characters — "pwke" is a subsequence of "pwwkew" but not a substring.

Examples

Input:  s = "abcabcbb"
Output: 3
Explanation: "abc" is the longest substring without repeats.

Input:  s = "bbbbb"
Output: 1
Explanation: Every substring longer than 1 contains two 'b's.

Input:  s = "pwwkew"
Output: 3
Explanation: "wke" has length 3. "pwke" is not contiguous, so it does not count.

Constraints

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

💡 Key Insight

If a window s[left..right] has no duplicates, every smaller window inside it also has none — so we never need to restart from scratch. Grow the window to the right; when the new character is already inside the window, move left just past its previous occurrence. Each index enters and leaves the window at most once, giving O(n).

Brute Force

TimeO(n · m)SpaceO(m)

Intuition

Start a substring at every index i and extend it to the right one character at a time, using a set to detect the first repeat. The moment a repeat appears, no longer substring starting at i can be valid, so stop and move to the next i.

Algorithm

best = 0.
For each start i:
- Create an empty set seen.
- For j from i while j < n: if s[j] is in seen, break; otherwise add it and update best = max(best, j - i + 1).
Return best.

Visualization

s = "abcabcbb"

i=0: a b c | a repeats → length 3
i=1: b c a | b repeats → length 3
i=2: c a b | c repeats → length 3
i=3: a b c | b repeats → length 3
...                       best = 3

Code

java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int best = 0;
        for (int i = 0; i < n; i++) {
            Set<Character> seen = new HashSet<>();
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                if (seen.contains(c)) {
                    break; // any longer substring from i also has this repeat
                }
                seen.add(c);
                best = Math.max(best, j - i + 1);
            }
        }
        return best;
    }
}

Complexity

Time: O(n · m) — for each start we scan at most m characters before a repeat, where m is the alphabet size (≤ 128); O(n²) in general.
Space: O(m) — the set holds at most one copy of each character.

Sliding Window with HashSet

TimeO(n)SpaceO(m)

Intuition

Instead of restarting at every i, keep one window [left, right] whose characters live in a set. When s[right] is already in the set, shrink from the left — removing characters — until the duplicate is gone. Then add s[right] and record the window size.

Algorithm

left = 0, empty set window, best = 0.
For right from 0 to n - 1:
- While s[right] is in window: remove s[left] and increment left.
- Add s[right]; best = max(best, right - left + 1).
Return best.

Dry Run

s = "pwwkew"

right=0 'p': window={p}        left=0  len=1
right=1 'w': window={p,w}      left=0  len=2
right=2 'w': dup → remove p, remove w → left=2, window={w}  len=1
right=3 'k': window={w,k}      left=2  len=2
right=4 'e': window={w,k,e}    left=2  len=3 ✓
right=5 'w': dup → remove w → left=3, window={k,e,w}  len=3
best = 3

Code

java

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> window = new HashSet<>();
        int left = 0;
        int best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // shrink until c is no longer inside the window
            while (window.contains(c)) {
                window.remove(s.charAt(left));
                left++;
            }
            window.add(c);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Complexity

Time: O(n) — each character is added once and removed at most once (≤ 2n set operations).
Space: O(m) — the set holds at most m distinct characters.

Sliding Window with Last-Seen IndexOptimal

TimeO(n)SpaceO(m)

Intuition

Shrinking one step at a time is wasteful: we already know where the duplicate is. Store the last index of every character. When s[right] was last seen at index k inside the current window (k >= left), jump left straight to k + 1. An int[128] array replaces the hash map since the input is ASCII.

Algorithm

lastIndex[128] filled with -1; left = 0, best = 0.
For right from 0 to n - 1:
- c = s[right]. If lastIndex[c] >= left, set left = lastIndex[c] + 1.
- lastIndex[c] = right.
- best = max(best, right - left + 1).
Return best.

Dry Run

flowchart TD
    A["s = 'abcabcbb', left = 0"] --> B["right 0..2: a, b, c new<br/>window 'abc', best = 3"]
    B --> C["right 3: 'a' last at 0 >= left<br/>left = 1, window 'bca'"]
    C --> D["right 4: 'b' last at 1 >= left<br/>left = 2, window 'cab'"]
    D --> E["right 5: 'c' last at 2 >= left<br/>left = 3, window 'abc'"]
    E --> F["right 6: 'b' last at 4 >= left<br/>left = 5, window 'cb'"]
    F --> G["right 7: 'b' last at 6 >= left<br/>left = 7, window 'b'"]
    G --> H["return best = 3"]

Code

java

import java.util.Arrays;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] lastIndex = new int[128]; // ASCII -> last position seen
        Arrays.fill(lastIndex, -1);
        int left = 0;
        int best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            // only jump if the previous occurrence is inside the current window
            if (lastIndex[c] >= left) {
                left = lastIndex[c] + 1;
            }
            lastIndex[c] = right;
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Complexity

Time: O(n) — exactly one pass; left only jumps forward.
Space: O(m) — a fixed 128-slot array (O(1) for a fixed alphabet).

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(m)
Sliding Window + HashSet	O(n)	O(m)
Sliding Window + Last Index	O(n)	O(m)

Common Pitfalls

Moving left backwards: with the last-index map, a character may have been seen before the window started. Always guard with lastIndex[c] >= left (or use left = max(left, last + 1)).
Confusing substring with subsequence — the characters must be contiguous.
Forgetting the empty string; the loop naturally returns 0, but code that indexes s.charAt(0) up front will crash.
Using a 26-slot array: the input includes digits, spaces and symbols, so use 128 (or a map).