Longest Substring Without Repeating Characters

Problem in Plain English

Given a string s, return the length of the longest contiguous substring in which every character appears exactly once.

Problem Statement

Given a string s, return the length of its longest contiguous substring with no repeated character. Characters next to each other in the answer must occupy adjacent positions in s; skipping a repeated character would create a subsequence, not a substring.

Return 0 for an empty input. Letter case, digits, punctuation, and spaces all participate in the same uniqueness rule.

Constraints

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

Examples

Example 1

Input: s = "abcabcbb"
Output: 3

The longest substring without repeating characters is "abc", with length 3.

Example 2

Input: s = "bbbbb"
Output: 1

Every longer window repeats "b", so the answer is "b" with length 1.

Example 3

Input: s = "pwwkew"
Output: 3

The longest substring without repeating characters is "wke", with length 3.

Example 4

Input: s = ""
Output: 0

There is no non-empty substring, so the maximum length is zero.

Example 5

Input: s = "abba"
Output: 2

The repeated b forces removal of both a and the earlier b. The longest valid windows are ab and ba, each length two.

Example 6

Input: s = "a A1!"
Output: 5

Lowercase a, a space, uppercase A, digit 1, and ! are five distinct characters. Spaces and case are significant.

Intuition

Keep a window of consecutive characters and remember exactly which characters it contains. In abcabcbb, the first abc is unique, but the next a repeats the window's a. Dropping that earlier a leaves bca, which is still a length-three candidate. Remove only enough of the left side to eliminate a repeat; preserving the remaining characters lets later windows grow without restarting.

Approaches

Brute Force

Solution Details

Reveal Brute Force: intuition, complexity, and code

Intuition

Every answer starts at some index, so we can try each start directly. From a fixed start we extend right with a set until the first repeat, and the distance reached is the best substring from that start.

Step-by-Step Logic

Set best = 0. For every start i, allocate a fresh seen set and scan end j from i onward.
If s[j] is already in seen, stop that start: any extension would still contain the repeated pair. Otherwise insert s[j] and update best from j - i + 1.
Example 1 starting at 0 inserts a, b, c, then stops at a at index 3. Starting at 1 inserts b, c, a and stops at b at 4.
Repeat all remaining starts, resetting seen each time. The last two starts each yield one b; no start yields a length above 3. Return 3.

Why It Works

Every candidate begins at an enumerated start. The set records exactly the characters collected since that start, so insertion is allowed precisely when extending keeps the substring unique. At the first repeat, the two equal characters remain in every longer substring with the same start; stopping cannot miss a valid extension. The greatest length over every start is therefore the global maximum.

Dry Run

Brute Force: variable states at each step
start,end	Character	Seen before	Action / seen after	Candidate length	Best after
`0,0`	`a`	`[]`	insert `["a"]`	`1`	`1`
`0,1`	`b`	`["a"]`	insert `["a","b"]`	`2`	`2`
`0,2`	`c`	`["a","b"]`	insert `["a","b","c"]`	`3`	`3`
`0,3`	`a`	`["a","b","c"]`	repeat; break	not valid	`3`
`1,1`	`b`	`[]`	insert `["b"]`	`1`	`3`
`1,2`	`c`	`["b"]`	insert `["b","c"]`	`2`	`3`
`1,3`	`a`	`["b","c"]`	insert `["b","c","a"]`	`3`	`3`
`1,4`	`b`	`["b","c","a"]`	repeat; break	not valid	`3`
`2,2`	`c`	`[]`	insert `["c"]`	`1`	`3`
`2,3`	`a`	`["c"]`	insert `["c","a"]`	`2`	`3`
`2,4`	`b`	`["c","a"]`	insert `["c","a","b"]`	`3`	`3`
`2,5`	`c`	`["c","a","b"]`	repeat; break	not valid	`3`
`3,3`	`a`	`[]`	insert `["a"]`	`1`	`3`
`3,4`	`b`	`["a"]`	insert `["a","b"]`	`2`	`3`
`3,5`	`c`	`["a","b"]`	insert `["a","b","c"]`	`3`	`3`
`3,6`	`b`	`["a","b","c"]`	repeat; break	not valid	`3`
`4,4`	`b`	`[]`	insert `["b"]`	`1`	`3`
`4,5`	`c`	`["b"]`	insert `["b","c"]`	`2`	`3`
`4,6`	`b`	`["b","c"]`	repeat; break	not valid	`3`
`5,5`	`c`	`[]`	insert `["c"]`	`1`	`3`
`5,6`	`b`	`["c"]`	insert `["c","b"]`	`2`	`3`
`5,7`	`b`	`["c","b"]`	repeat; break	not valid	`3`
`6,6`	`b`	`[]`	insert `["b"]`	`1`	`3`
`6,7`	`b`	`["b"]`	repeat; break	not valid	`3`
`7,7`	`b`	`[]`	insert `["b"]`	`1`	`3`
Finish	none	fresh set at each start	all starts finished	none	return `3`

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(\min(n,m))

Let n be string length and m the number of available distinct character values. Each start checks at most min(n, m) distinct characters and possibly one repeat, giving O(n * min(n, m)) expected hash-set work and the usual O(n^2) upper bound when the alphabet can grow with n. A fresh set holds at most min(n, m) entries, so extra space is O(min(n, m)); a fixed finite alphabet gives a tighter time bound.

Code

Solution.java

1import java.util.Set;2import java.util.HashSet;3
4class Solution {5    public int lengthOfLongestSubstring(String s) {6        int n = s.length();7        int best = 0;8        for (int i = 0; i < n; i++) {9            Set<Character> seen = new HashSet<>();10            for (int j = i; j < n; j++) {11                char c = s.charAt(j);12                if (seen.contains(c)) {13                    break;14                }15                seen.add(c);16                if (j - i + 1 > best) {17                    best = j - i + 1;18                }19            }20        }21        return best;22    }23}

Hints

Hint 1

Fix a start index and grow the window to the right until a character repeats: everything before the repeat is a valid substring.

Hint 2

When the right edge hits a duplicate, the window can only become valid again by dropping characters from the left, one at a time, until the duplicate is gone.

Hint 3

A hash set holding exactly the current window makes both the duplicate test and the left-edge removals constant time.

Edge Cases

The empty string returns 0 without entering either scan.
A uniform string such as bbbbb returns 1; a fully distinct string such as abcdef returns its full length 6.
Repeated characters separated by others may require several left removals: abba returns 2, not 3 or 4.
Spaces, punctuation, digits, and case are significant: a space repeated twice is a duplicate, while a and A differ.
Substring continuity matters: pwwkew has answer 3; selecting pwke skips a position and is not a valid answer.
For the stated English-character inputs the three implementations agree. If extended to arbitrary supplementary Unicode, Java/JavaScript indexing uses UTF-16 code units while Python uses code points; choose consistent character units before reusing the snippets.

Common Mistakes and Interview Tips

Using if instead of while for duplicate removal may leave the duplicate inside the window after only one removal.
Clearing the whole set when a repeat arrives loses useful suffix candidates; remove only through the earlier occurrence.
Adding the incoming character before shrinking destroys the exact relationship between the set and the current window. Shrink first, then insert.
Computing length as right - left instead of right - left + 1 drops one character.
Interview tip: explain why the set matches the current unique window, and why both pointers move only forward. A nested loop is still linear here because each left removal happens at most once per position.

Key Takeaway

A sliding window plus a set turns uniqueness constraints into a one-pass scan: expand until the rule breaks, then shrink from the left just enough to restore it.