Problem 7.2 · Sliding WindowMedium

Longest Substring Without Repeating Characters

PatternSliding Window: Variable Size Hash Map Lookup (Complement)

What it teaches: The variable window for "longest": grow right, and when a character repeats, jump left past its previous position.

Practise it on judges as “Longest Substring Without Repeating Characters”.

The problem

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

Example 1

Input: s = "abcabcbb"
Output: 3

"abc".

Example 2

Input: s = "bbbbb"
Output: 1

Example 3

Input: s = "pwwkew"
Output: 3

"wke". "pwke" is a subsequence, not a substring.

Constraints

0 ≤ s.length ≤ 5 × 10⁴
Letters, digits, symbols and spaces

Pattern clues in the wording

→ "Longest substring" with a condition
→ Condition breaks when a character repeats; removing from the left fixes it

These clues point to Sliding Window: Variable Size: Grow the window with the right pointer; when it breaks a rule, shrink it from the left until it's valid again.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0, best = 0;
        return best;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	s = "abcabcbb"	3
2	s = "bbbbb"	1
3	s = "pwwkew"	3
4	s = ""	0

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Window with a set · O(n)2. Optimal: jump using last-seen indexes · O(n)

Window with a set

Time O(n) Space O(alphabet)

Grow right; while s[right] is already in the window's set, remove s[left] and advance left. Then add s[right] and record the length.

Approach 1

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

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

Verdict: Linear: each character is added and removed once.

Optimal: jump using last-seen indexes

Time O(n) Space O(alphabet)

Store each character's last index. When s[right] was last seen at or after left, jump left to that index + 1 in one step.

▶ Dry run: Jumping the left edges = "pwwkew"

↑L

↑R

last index(map)

p: 0w: 1

best(vars)

Step 1/4"pw": no repeats. best = 2.

Approach 2

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

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int left = 0, best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            Integer prev = last.get(c);
            if (prev != null && prev >= left) left = prev + 1;   // only jump forward
            last.put(c, right);
            best = Math.max(best, right - left + 1);
        }
        return best;
    }
}

Verdict: Each step is O(1); no inner loop.

Before you submit

Edge cases and common mistakes

Test these inputs

Empty string → 0
All the same character
All distinct
Spaces and symbols count as characters

Mistakes people make

Moving left backwards when the repeat was before the window (prev >= left check).
Confusing substring with subsequence.

Interview

Follow-up questions

What if at most k distinct characters are allowed?

Command Palette