Longest Substring Without Repeating Characters: Sliding window Pattern

Learning Outcome

After this lesson, you should be able to maintain a duplicate-free window and move the left boundary only when a repeated character breaks the window.

Problem Statement

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

Brute Force Approach

Start from every index and extend until a duplicate appears. Track the maximum valid length.

This repeats scans from many start positions, so the worst-case time is O(n^2).

Optimized Approach

Use a sliding window [left, right]. Store the last index where each character appeared. When the current character was seen inside the current window, move left just after that old index.

Never move left backward. That one rule keeps the window valid and linear.

Exact Pseudocode

lastSeen = empty map
left = 0
best = 0
for right from 0 to length(s) - 1:
  char = s[right]
  if char exists in lastSeen and lastSeen[char] >= left:
    left = lastSeen[char] + 1
  lastSeen[char] = right
  best = max(best, right - left + 1)
return best
  

Reference Code

class Solution:
    def lengthOfLongestSubstring(self, s):
        last_seen = {}
        left = 0
        best = 0

        for right, ch in enumerate(s):
            if ch in last_seen and last_seen[ch] >= left:
                left = last_seen[ch] + 1
            last_seen[ch] = right
            best = max(best, right - left + 1)

        return best
  

Sample Dry Run

Complexity

Edge Cases

• Empty string returns 0.
• All characters same returns 1.
• Repeated character appears before the current window and should not move left backward.

Interview Checklist

• Define the window invariant: no duplicate characters inside it.
• Use last seen index to jump left.
• Update answer after fixing the window.

FAQs

A set works too, but last seen index lets you jump the left boundary directly.

It prevents moving left backward when a duplicate is outside the current window.

Sliding window with last-seen positions.