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

Time complexity: O(n). Space complexity: O(min(n, m)).

Longest Substring Without Repeating Characters

Med

Concept

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Longest Substring Without Repeating Characters

Approach

Maintain a variable-size window with a Map storing each character and its most recent index. Expand right one character at a time. When a duplicate is found and its last index is within the current window, jump the left pointer past it. Track the maximum window length throughout.

Complexity Analysis

Time: O(n)
Space: O(min(n, m))

Pattern

Sliding Window (Variable Size)

Why It Works

The Map lets us instantly detect duplicates and know where to move the left pointer. By jumping left directly past the duplicate instead of shrinking one step at a time, each character is processed at most twice (once by right, once by left), giving linear time.

Updated Feb 2026