Longest Substring Without Repeating Characters
Maintained by Vikas D, software engineer
You are handed a string `s` and asked for a single number: the length of the longest stretch of adjacent characters that are all distinct. A stretch here means a contiguous slice of the string, so the characters you pick must sit next to each other rather than being scattered.
The moment a character would appear twice inside the slice you are tracking, that slice is no longer valid and cannot be counted. You want the longest valid slice anywhere in the string.
Characters can be any letter, digit, symbol, or space, and the string may be empty. For an empty string the answer is 0, since there is no slice at all. Note the difference from a subsequence problem: you may not skip over characters in the middle, the winning slice has to be one unbroken segment.
Examples
The slice "abc" has three distinct characters. Any attempt to extend further hits a repeat, so 3 is the best.
Every character is the same, so the longest slice without a repeat is a single "b".
"wke" is the longest valid slice. Note "pwke" is not a substring because it skips a character, and "pww" repeats w.
When the second d appears, the window slides past the first d, leaving "vdf" of length 3.
Constraints
- 0 <= s.length <= 5 * 10^4
- s may contain English letters, digits, symbols, and spaces
- The empty string returns 0
Visible test cases
- lengthOfLongestSubstring("abcabcbb") == 3
- lengthOfLongestSubstring("bbbbb") == 1
- lengthOfLongestSubstring("pwwkew") == 3
- lengthOfLongestSubstring("") == 0
- lengthOfLongestSubstring("abcdef") == 6
- lengthOfLongestSubstring("dvdf") == 3
- lengthOfLongestSubstring(" ") == 1
Hints
Hint 1
A brute-force check of every possible slice works but is slow. Think about what changes when you grow a slice one character to the right.
Hint 2
Keep a sliding window with a left and right edge. When the character at the right edge already lives inside the window, you must move the left edge forward to drop the earlier copy.
Hint 3
Instead of moving the left edge one step at a time, store the last index at which you saw each character. That lets you jump the left edge directly past the previous occurrence in one move.
Approaches
Brute force over all substrings
Time O(n^2) · Space O(min(n, k)) where k is the alphabet sizeCheck every starting position, extend as far as possible while characters stay unique, and track the longest length found.
- For each start index i, create an empty set of seen characters.
- Walk forward from i, adding each character to the set.
- Stop the inner walk the first time a character is already in the set.
- Record the length reached and keep the maximum across all starts.
Sliding window with last-seen index map
Time O(n) · Space O(min(n, k)) where k is the alphabet sizeMaintain a window of distinct characters using a left pointer, and store the most recent index of each character so the left pointer can jump instead of crawl.
- Keep a map from character to its last seen index, a window start at 0, and a best length at 0.
- Scan with a right pointer i over the string.
- If the current character was seen at an index at or after start, move start to one past that index so the duplicate falls outside the window.
- Update the character's last seen index to i, then update best with the current window length i - start + 1.
- Return best after the scan.
Common mistakes
- Forgetting the guard that the previous occurrence must be at or after `start`. Without it, a stale earlier index pulls the window start backwards and shrinks valid windows.
- Treating this as a subsequence and allowing skipped characters. The answer must be a contiguous substring.
- Returning the substring itself or its character set instead of the integer length.
- Mishandling the empty string. The loop never runs, so best stays 0, which is correct only if you initialize best to 0.
Follow-up variations
- Return the actual longest substring, not just its length, and decide how to break ties between equal-length winners.
- Generalize to the longest substring with at most k distinct characters.
- Handle a streaming input where characters arrive one at a time and you must report the running answer.
- Bound the auxiliary space by a fixed-size array when the alphabet is known and small, such as ASCII.