Longest Substring With All Unique Characters

Medium20–25 min

Topics

StringSliding WindowHash Table

Companies

AmazonMicrosoftGoogleAdobeBloomberg

Given a string s, return the length of the longest substring that contains no repeated characters. Checking every starting index and re-scanning forward works, but it forgets everything the previous start already learned about the string. The sliding window technique keeps a hash map of each character's most recent index: grow the window by moving the right edge forward, and whenever a character repeats inside the current window, jump the left edge straight past that character's earlier occurrence — no need to shrink one step at a time. Every character is visited once by the right pointer, so the whole scan runs in O(n).

Test Case 1:

Input:s = "abcba"

Output:3

Explanation:"abc" is the longest substring with no repeated characters.

Test Case 2:

Input:s = "bbbbb"

Output:1

Explanation:Every character repeats immediately, so the longest valid window has length 1.

Test Case 3:

Input:s = "pwwkew"

Output:3

Explanation:"wke" is the longest substring with no repeated characters.

Constraints

◆0 ≤ s.length ≤ 5 × 10⁴
◆s consists of English letters, digits, symbols, and spaces

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s — 2-10 characters (letters, digits, symbols, spaces)

1	class Solution {
2	public int lengthOfLongestUniqueSubstring(String s) {
3	Map<Character, Integer> lastSeen = new HashMap<>();
4	int left = 0, maxLen = 0;
5	for (int right = 0; right < s.length(); right++) {
6	char c = s.charAt(right);
7	if (lastSeen.containsKey(c) && lastSeen.get(c) >= left) {
8	left = lastSeen.get(c) + 1;
9	}
10	lastSeen.put(c, right);
11	maxLen = Math.max(maxLen, right - left + 1);
12	}
13	return maxLen;
14	}
15	}
16

Variables

left0

maxLen0

INITIALIZE

Start left at 0, maxLen at 0, and an empty map of each character's most recent index.

Step 1 / 13

Approach & Solutions

Brute Force

Brute

For every possible starting index, grow the window to the right — tracking the characters seen so far in a set — until a repeat would enter, then record the window's length. Correct, but every start re-scans from scratch, throwing away everything the previous start already discovered about the string.

TimeO(n²)

SpaceO(n)

Java

Try it out

class Solution {
    public int lengthOfLongestUniqueSubstring(String s) {
        int maxLen = 0;
        for (int i = 0; i < s.length(); i++) {
            Set<Character> seen = new HashSet<>();
            int j = i;
            while (j < s.length() && !seen.contains(s.charAt(j))) {
                seen.add(s.charAt(j));
                j++;
            }
            maxLen = Math.max(maxLen, j - i);
        }
        return maxLen;
    }
}

Optimal — Sliding Window

Optimal

Slide a window right, tracking each character's most recent index in a hash map. When a character repeats and its last occurrence lies inside the current window, jump the left edge forward to just past that occurrence instead of shrinking one step at a time. Every character is visited once by the right pointer, so the whole scan runs in O(n).

TimeO(n)

SpaceO(min(n, charset))