Skip to main content
Ace Hired
All coding problems

Longest Substring Without Repeating Characters

Mediumsliding windowSliding window with a hash map of last-seen indicessliding-windowstringshash-map

Maintained by Vikas D, software engineer

You are handed a string `s` that may contain letters, digits, symbols, or spaces. Your job is to find a contiguous slice of it where every character is distinct, and report how long the longest such slice can be.

The slice must be contiguous, so you cannot skip over characters and stitch the remaining ones together. Once a character would appear twice inside your current slice, that slice is no longer valid and the count for it stops.

Return only the length of the best slice, not the slice itself. An empty input has no characters, so the answer there is 0.

Examples

Input: s = "abcabcbb"
Output: 3

The slice "abc" has three distinct characters. Extending it to "abca" repeats 'a', so 3 is the most you can reach anywhere in the string.

Input: s = "pwwkew"
Output: 3

"wke" is a valid window of length 3. "pww" fails because 'w' repeats, and no window beats 3.

Input: s = "dvdf"
Output: 3

When the second 'd' is reached, the window resets to start just after the first 'd', giving "vdf" of length 3 rather than collapsing all the way back to the start.

Constraints

  • 0 <= s.length <= 5 * 10^4
  • s may contain English letters, digits, symbols, and spaces
  • The answer is a single integer: the length of the longest valid window

Visible test cases

  • lengthOfLongestSubstring("abcabcbb") == 3
  • lengthOfLongestSubstring("bbbbb") == 1
  • lengthOfLongestSubstring("pwwkew") == 3
  • lengthOfLongestSubstring("") == 0
  • lengthOfLongestSubstring("abcdefg") == 7
  • lengthOfLongestSubstring("dvdf") == 3
  • lengthOfLongestSubstring("anviaj") == 5

Hints

Hint 1

Think about a window that expands to the right and only shrinks from the left when it has to. You never need to move the right edge backward.

Hint 2

When you read a character you have seen before, the left edge of the window cannot stay where it was. It must jump to just past that character's previous position.

Hint 3

Store the most recent index of each character. When a repeat shows up, advance the window start to that stored index plus one, but only forward, never backward.

Loading the editor...

Approaches

Brute force over all substrings

Time O(n^2) in the worst case, since each start can scan most of the remaining string · Space O(min(n, k)) for the set, where k is the size of the character alphabet

Check every possible substring and keep the length of the longest one whose characters are all unique.

  1. For each start index i, extend an end index j to the right.
  2. Track the characters seen since i in a set.
  3. As soon as a character already in the set appears, stop extending this start and move on.
  4. Record the largest window length found across all starts.

Optimal sliding window with last-seen index

Time O(n), each character is visited once and the left edge only moves forward · Space O(min(n, k)) for the map, bounded by the alphabet size

Keep one window over the string and remember the last position of every character. When a character repeats inside the window, slide the left edge forward in a single jump instead of re-scanning.

  1. Keep a map from character to its most recent index, plus a `start` marker for the window's left edge.
  2. Walk the right edge `i` across the string one character at a time.
  3. If the current character was seen at an index that is still inside the window (its last index is at least `start`), set `start` to that last index plus one.
  4. Update the character's last-seen index to `i`.
  5. The current window length is `i - start + 1`; track the maximum of these.

Common mistakes

  • Moving `start` backward when a repeat sits to the left of the current window. The 'dvdf' case breaks if you jump to a stale previous index instead of guarding with `last index >= start`.
  • Forgetting to update a character's stored index to the current position after handling a repeat, which corrupts later window resets.
  • Returning the substring or its end position rather than the length the prompt asks for.
  • Treating only letters as valid and ignoring digits, symbols, or spaces, which the input is allowed to contain.
  • Mishandling the empty string by indexing into it instead of returning 0.

Follow-up variations

  • Return the actual longest substring, not just its length, including a tie-break rule when several share the maximum length.
  • Allow up to k repeated characters inside the window instead of zero, which turns this into a longest-substring-with-at-most-k-distinct style problem.
  • Report the count of all distinct windows that achieve the maximum length.
  • Handle a streaming input where characters arrive one at a time and you must report the best length so far without storing the whole string.

Recommended problems

Build the rest of your prep