Developers

Longest Substring Without Repeating Characters

MediumSliding windowGrade AAlso known as LeetCode 3

You get a string s. A substring is a run of characters that sit next to each other in s.

Return the length of the longest substring in which no character appears more than once.

Examples

Input s = "abcabcbb"
Output 3
The longest is "abc".
Input s = "bbbbb"
Output 1
Only a single b fits.
Input s = "pwwkew"
Output 3
"wke" has length 3. "pwke" would skip a letter, so it is not a substring.

Constraints

  • 0 <= s.length <= 50,000
  • s may contain letters, digits, symbols and spaces

Stuck? Take one hint at a time

Common mistakes
  • Moving the left edge backward when the earlier copy is already outside the window.
  • Resetting the whole window to start at the repeat instead of jumping past the old copy.
  • Forgetting the empty string, whose answer is 0.
  • Measuring the length as i - start instead of i - start + 1.
Questions an interviewer may ask next
  • Return the substring itself, not just its length.
  • Allow at most k distinct characters instead of none repeating.
  • Allow each character to repeat at most twice.
  • The input is a stream. What do you keep?

How often this is reported

Commonly reported across 16 of 25 tracked companies
16/25

Grade A: Reported in several independent candidate sources. This reflects what candidates report, not a guarantee of what any company will ask.