Longest Substring Without Repeating Characters

Return the length of the longest substring that contains no repeated characters.

Open concept page Back to problem map

This is a signature variable-size sliding window problem.

It teaches how a window stays valid by shrinking only as much as necessary.

Problem intuition

The naive version grows a substring from every starting point until a repeat appears.

The optimal solution treats the substring as a sliding window and shrinks it only when a repeated character breaks validity.

Java solution ladder

The solutions below are ordered from least optimal to most optimal, so you can see the improvement path instead of only the final answer.

Solution 1

Restart from every index

O(n^2)O(min(n, charset))

Build a fresh set for every start index and extend until a duplicate appears. Correct, but it revisits too much work.

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

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int best = 0;

        for (int start = 0; start < s.length(); start++) {
            Set<Character> seen = new HashSet<>();

            for (int end = start; end < s.length(); end++) {
                char ch = s.charAt(end);
                if (seen.contains(ch)) {
                    break;
                }

                seen.add(ch);
                best = Math.max(best, end - start + 1);
            }
        }

        return best;
    }
}

Solution 2

Sliding window with character counts

O(n)O(min(n, charset))

Expand right, and while the latest character is duplicated, move left until the window becomes valid again.

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

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> counts = new HashMap<>();
        int left = 0;
        int best = 0;

        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            counts.put(ch, counts.getOrDefault(ch, 0) + 1);

            while (counts.get(ch) > 1) {
                char leftChar = s.charAt(left);
                counts.put(leftChar, counts.get(leftChar) - 1);
                left++;
            }

            best = Math.max(best, right - left + 1);
        }

        return best;
    }
}