How do you approach Longest Substring Without Repeating Characters?

Use a sliding window approach with two pointers.

What is the time complexity of Longest Substring Without Repeating Characters?

Time complexity: O(n). Space complexity: O(min(m, n)) where m is the character set size.

What are common mistakes on Longest Substring Without Repeating Characters?

Shrinking with if instead of while - one removal is often not enough to restore the invariant. Recomputing the window's contents each step, which puts back the O(n²) the pattern exists to remove. Never recording the answer for a window that ends at the last index.

gitGood.dev

← Back to problems

Longest Substring Without Repeating Characters

MediumAlgorithms

Description

Given a string s, find the length of the longest substring without repeating characters.

Example 1

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2

Input: s = "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3

Input: s = "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3. Note that "pwke" is a subsequence and not a substring.

Constraints

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

Longest Substring Without Repeating Characters: approach, complexity and pitfalls

A medium sliding window problem, graded against 7 test cases (4 of them hidden).

The pattern: Sliding Window

A moving window over a contiguous run, expanding and contracting to hold an invariant.

Reach for it when you see: "Longest/shortest contiguous subarray or substring satisfying X."

If you are stuck

Show the 3-step hint ladder

Use a sliding window approach with two pointers.
Use a Set or Map to track characters in the current window.
When you find a duplicate, shrink the window from the left until the duplicate is removed.

The optimal approach

Show the approach: Sliding Window with Hash Set

Use two pointers to define a window. Expand the right pointer and add characters to a set. When a duplicate is found, shrink from the left.

Time: O(n)
Space: O(min(m, n)) where m is the character set size

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty string. An empty string is passed, so index reads and any assumption of at least one character are tested.

Common Sliding Window mistakes

These apply to the pattern as a whole, not just this problem.

Shrinking with `if` instead of `while` - one removal is often not enough to restore the invariant.
Recomputing the window's contents each step, which puts back the O(n²) the pattern exists to remove.
Never recording the answer for a window that ends at the last index.

← Back to problems

Longest Substring Without Repeating Characters

MediumAlgorithms

Description

Given a string s, find the length of the longest substring without repeating characters.

Example 1

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2

Input: s = "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3

Input: s = "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3. Note that "pwke" is a subsequence and not a substring.

Constraints

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

Longest Substring Without Repeating Characters: approach, complexity and pitfalls

A medium sliding window problem, graded against 7 test cases (4 of them hidden).

The pattern: Sliding Window

A moving window over a contiguous run, expanding and contracting to hold an invariant.

Reach for it when you see: "Longest/shortest contiguous subarray or substring satisfying X."

If you are stuck

Show the 3-step hint ladder

Use a sliding window approach with two pointers.
Use a Set or Map to track characters in the current window.
When you find a duplicate, shrink the window from the left until the duplicate is removed.

The optimal approach

Show the approach: Sliding Window with Hash Set

Use two pointers to define a window. Expand the right pointer and add characters to a set. When a duplicate is found, shrink from the left.

Time: O(n)
Space: O(min(m, n)) where m is the character set size

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty string. An empty string is passed, so index reads and any assumption of at least one character are tested.

Common Sliding Window mistakes

These apply to the pattern as a whole, not just this problem.

Shrinking with `if` instead of `while` - one removal is often not enough to restore the invariant.
Recomputing the window's contents each step, which puts back the O(n²) the pattern exists to remove.
Never recording the answer for a window that ends at the last index.