RTE logo
← Back to DSA map
Sliding Window

Longest Substring Without Repeating Characters

Length of the longest substring with all-distinct characters.

Medium

Problem

Given a string s, return the length of the longest substring that contains no repeating characters.

  • A substring is contiguous - "pwke" in "pwwkew" is a subsequence, not a substring.
  • The empty string has length 0.

Examples

Input: s = "abcabcbb"
Output: 3
"abc"
Input: s = "bbbbb"
Output: 1
"b"
Input: s = "pwwkew"
Output: 3
"wke"

Approach

Time O(n)Space O(min(n, charset))
  1. Keep a stretch of the string from L to R that has no repeats, plus a map from each character to the last position you saw it.
  2. Move R forward one character at a time.
  3. If the character was last seen inside the window (lastSeen >= L), jump L to lastSeen + 1 so the window is valid again.
  4. Record its new position, then update best with the window length R - L + 1.

Brute force: Start at every position and extend, using a set, until a character repeats - a loop inside a loop.

Common mistakes

  • Jumping L to lastSeen + 1 without checking lastSeen >= L can move L backwards to a stale position.
  • Removing characters one by one from a set also works, but takes more steps than jumping L.

Step through it

Pick an input and play the algorithm step by step. The highlighted line in the code follows each step, and you can edit the code to experiment.

SW
Solution · JS
Window · L=—  R=—
a0
b1
c2
a3
b4
c5
b6
b7
MAP{ }
Left
—
Right
—
Win
0
Best
0
Step
—
0 / 0
1×
Execution log
steps appear here…

Solution

The same approach in JavaScript, Python, and Java. Each is a complete program that prints the examples above - JavaScript runs here, so edit it and try your own input.

Edit and run it here

JavaScript solution

Loading...

Output

Run code to see output...

Comments

Sign in to leave a comment. Your name and photo come from Google; nothing else is shared.

Loading comments...