Code Logo

Longest Substring Without Repeating Characters

Published at16 Mar 2026
Created by
Medium 21 views
Like0

You are given a string and need to find the length of the longest substring that contains no repeated characters.

The word substring matters here. The characters must come from one continuous stretch of the original string. You are not allowed to skip around and build a custom sequence from scattered positions.

For example, in "abcabcbb", the best unique substring is "abc", so the answer is 3. In "bbbbb", every longer stretch repeats "b", so the best answer is only 1. In "pwwkew", one valid best substring is "wke", which also has length 3.

So the task is to measure the longest unbroken window of characters that stays fully unique.

Example Input & Output

Example 1
Input
s = "abcabcbb"
Output
3
Explanation

Longest unique substring is "abc".

Example 2
Input
s = "bbbbb"
Output
1
Explanation

Longest unique substring is "b".

Example 3
Input
s = "pwwkew"
Output
3
Explanation

Longest unique substring is "wke".

Algorithm Flow

Recommendation Algorithm Flow for Longest Substring Without Repeating Characters
Recommendation Algorithm Flow for Longest Substring Without Repeating Characters

Solution Approach

The best pattern here is a sliding window with a hash map that remembers the most recent index of each character.

Think of the current window as the substring between two pointers, left and right. As right moves through the string, we keep trying to extend the window. If the new character has not appeared inside the current window, we are fine and can simply update the best length.

The interesting case is when the new character has already been seen. We do not restart from scratch. Instead, we move left just past that character's last seen position. That removes the duplicate from the window while keeping as much of the current substring as possible.

A hash map makes this efficient because it tells us exactly where each character was last seen. The core update is:

left = Math.max(left, lastSeen.get(ch) + 1)

Then we store the new index for that character and compute the current window length with right - left + 1.

This works in O(n) time because each pointer only moves forward, and the map gives constant-time lookups. It is much faster than checking every substring, and it stays tightly focused on the continuous window the problem actually asks for.

Best Answers

java
import java.util.*;
class Solution {
    public int longest_substring_without_repeating_characters(String s) {
        Map<Character, Integer> last = new HashMap<>();
        int left = 0, ans = 0;
        for (int right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            if (last.containsKey(ch) && last.get(ch) >= left) {
                left = last.get(ch) + 1;
            }
            last.put(ch, right);
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}