What pattern does Longest Substring Without Repeating Characters use?

The Pattern: Sliding Window (Dynamic Window Adjustment) The Heuristic: Maintain a window with unique elements by expanding the right pointer and moving the left pointer forward only when duplicates are detected, using a hash map to track last seen positions for constant-time duplicate detection and window adjustment.

Longest Substring Without Repeating Characters

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

O(n). Each character is visited at most twice: once when the right pointer advances and once when the left pointer moves forward to remove duplicates. Hash map lookups and updates are O(1) on average.

Problem

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

0 ≤ s.length ≤ 5 * 10⁴
s consists of English letters, digits, symbols and spaces.

Example

Input: s = "abcabcbb"

Output: 3

The longest substring without repeating characters is "abc", which has length 3. The algorithm uses a sliding window to track the current substring without duplicates. Starting with an empty window, it expands the right pointer to include new characters. When a duplicate character is encountered, the left pointer moves forward to exclude the previous occurrence, ensuring the substring remains unique. This dynamic adjustment maintains the longest valid substring seen so far.

Approach

Straightforward Solution

A brute-force approach would check every possible substring and verify if it contains duplicates, resulting in O(n^3) time complexity due to substring generation and duplicate checks. This is inefficient for large inputs.

Core Observation

A substring without repeating characters can be represented as a contiguous window in the string where all characters are unique. The problem reduces to finding the maximum length of such a window.

Path to Optimal

Preview

The key recognition signals are 'longest substring' (implying contiguous sequence) and 'without repeating characters' (implying uniqueness constraint)…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers, left and right, to represent the current window. Iterate right over the string, and for each character, if it has been seen before and its last seen index is within the current window, move left to one position after that index to exclude the duplicate…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each character is visited at most twice: once when the right pointer advances and once when the left pointer moves forward to remove duplicates. Hash map lookups and updates are O(1) on average.

Space

O(min(m, n))

The hash map stores the last seen index of characters currently in the window. In the worst case, the window contains all unique characters, so the space is proportional to the size of the character set or the string length, whichever is smaller.

Solution

Python

1class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
      char_index_map = {}
      left = 0
      max_length = 0
6
      for right in range(len(s)):
          char = s[right]
          if char in char_index_map:
              left = max(char_index_map[char] + 1, left)
          
          char_index_map[char] = right
          max_length = max(max_length, right - left + 1)
      
      return max_length

Step-by-Step Solution

1

Track Character Indices and Window Boundaries to Maintain Uniqueness

3char_index_map = {}
4left = 0
5max_length = 0
7for right in range(len(s)):
8    char = s[right]
9    if char in char_index_map:
10        left = max(char_index_map[char] + 1, left)
12    char_index_map[char] = right

Objective

To maintain a mapping of characters to their most recent indices and dynamically adjust the window's left boundary to exclude duplicates.

Key Insight

By storing the last seen index of each character, the algorithm can detect duplicates within the current window in constant time. When a duplicate is found, moving the left pointer to one position after the previous occurrence removes the duplicate from the window. Using max ensures the left pointer never moves backward, preserving the window's integrity. This dynamic adjustment maintains a valid substring without duplicates at all times.

Interview Quick-Check

Core Logic

Use a hash map to store the last seen index of each character and update the left pointer to exclude duplicates by moving it to max(previous index + 1, current left).

State & Boundaries

The window is defined by [left, right], and left only moves forward to maintain a valid substring without duplicates.

Common Pitfalls & Bugs

Failing to use max when updating left can cause the left pointer to move backward, invalidating the window and causing incorrect results.

Complexity

Each character is processed once by the right pointer and at most once by the left pointer, ensuring O(n) time complexity.

2

Update Maximum Length Based on Current Window Size

To continuously track and update the length of the longest substring without repeating characters found so far.

3

Return the Length of the Longest Unique Substring

To provide the final result representing the maximum length of a substring without repeating characters.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 10 Critical

left = max(char_index_map[char] + 1, left)

Move the left pointer to exclude the previous occurrence of the duplicate character.

This line is the core of the sliding window adjustment; it prevents the left pointer from moving backward and guarantees the window always contains unique characters by skipping past the last duplicate's position.

Line 9 Critical

if char in char_index_map:

Check if the current character has been seen before in the window.

This conditional is the key to detecting duplicates within the current window, enabling the algorithm to maintain the uniqueness constraint by adjusting the left pointer.

Line 13 Critical

max_length = max(max_length, right - left + 1)

Update the maximum length found so far based on the current window size.

This line captures the global maximum substring length by comparing the current window size, which is essential for the correctness of the final result.

Full line-by-line criticality + rationale for all 10 lines available on Pro.

Test Your Understanding

Why must the left pointer move to max(char_index_map[char] + 1, left) instead of simply char_index_map[char] + 1?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Longest Substring Without Repeating Characters from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Longest Substring Without Repeating Characters drill

or drill a free problem

1	`class Solution:`
2	`def lengthOfLongestSubstring(self, s: str) -> int:`
3	`char_index_map = {}`
4	`left = 0`
5	`max_length = 0`
6
7	`for right in range(len(s)):`
8	`char = s[right]`
9	`if char in char_index_map:`
10	`left = max(char_index_map[char] + 1, left)`
11
12	`char_index_map[char] = right`
13	`max_length = max(max_length, right - left + 1)`
14
15	`return max_length`

3	`char_index_map = {}`
4	`left = 0`
5	`max_length = 0`
7	`for right in range(len(s)):`
8	`char = s[right]`
9	`if char in char_index_map:`
10	`left = max(char_index_map[char] + 1, left)`
12	`char_index_map[char] = right`