Problem Statement

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

A substring is a contiguous sequence of characters within a string.

Example 1

Input: s = "zxyzxyz"

Output: 3

Explanation:
The longest substring without repeating characters is "xyz".

Example 2

Input: s = "xxxx"

Output: 1

Constraints

  • 0 <= s.length <= 1000
  • s consists of printable ASCII characters.

Intuition

The goal is to find the longest continuous part of the string where every character is unique.

For example,

s = "abcabcbb"

Possible substrings without repeating characters are:

"a"      -> 1
"ab"     -> 2
"abc"    -> 3
"bca"    -> 3
"cab"    -> 3

The answer is 3.

There are multiple ways to solve this problem, each improving upon the previous one.

Solution 1: Brute Force

Idea

Start from every index and keep extending the substring until a duplicate character appears.

To quickly check whether we’ve already seen a character, we use a set.

For every starting position:

  1. Create an empty set.
  2. Move forward character by character.
  3. If the character is already in the set, stop.
  4. Otherwise, insert it and update the maximum length.

Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        count = 0

        for i in range(len(s)):
            charSet = set()

            for j in range(i, len(s)):
                if s[j] in charSet:
                    break

                charSet.add(s[j])
                count = max(count, len(charSet))

        return count

Dry Run

Let’s use

s = "zxyzxyz"

Start at index 0

{}
↓
z  -> {z}         length = 1
x  -> {z,x}       length = 2
y  -> {z,x,y}     length = 3
z  -> duplicate → stop

Maximum = 3

Start at index 1

{}
↓
x -> {x}
y -> {x,y}
z -> {x,y,z}
x -> duplicate

Maximum remains 3

The same process repeats for every index.

Complexity Analysis

Time Complexity

The outer loop runs n times.

For every starting position, the inner loop may also scan up to n characters.

O(n²)

Space Complexity

The set can contain at most every unique character.

O(min(n, charset))

For ASCII characters, this is effectively constant, but generally we write:

O(n)

Solution 2: Sliding Window (Optimal)

The brute-force solution repeats a lot of work.

Suppose we’ve already examined the substring:

xyz

When we encounter another x, instead of starting over, we can simply shrink the current window from the left until the duplicate is removed.

This is exactly what the Sliding Window technique does.

Idea

Maintain a window with two pointers:

  • l → left boundary
  • r → right boundary

The window always contains unique characters only.

For every character:

  • If it’s new, expand the window.
  • If it’s already inside the window, remove characters from the left until the duplicate disappears.
  • Update the maximum window size.

Visualization

Consider

s = "zxyzxyz"

Initially

Window = ""

Step 1

l
↓
z
↑
r

Window:

z

Length = 1

Step 2

l
↓
zx
 ↑
 r

Window:

zx

Length = 2

Step 3

l
↓
zxy
  ↑
  r

Window:

zxy

Length = 3

Step 4

Next character is another z.

Current window:

zxy

Since z already exists:

Remove characters from the left.

Remove first z

xy

Now insert new z

xyz

The window is valid again.

Maximum length remains 3.

Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        charSet = set()
        l = 0
        count = 0

        for r in range(len(s)):
            while s[r] in charSet:
                charSet.remove(s[l])
                l += 1

            charSet.add(s[r])
            count = max(count, r - l + 1)

        return count

Why Does This Work?

The sliding window always satisfies one important condition:

Every character inside the window is unique.

Whenever a duplicate appears:

  • We don’t discard the whole substring.
  • We only remove enough characters from the left to eliminate the duplicate.
  • Then we continue expanding.

Each character is:

  • Added to the set once
  • Removed from the set once

This is why the algorithm runs in linear time.

Complexity Analysis

Time Complexity

Although there is a while loop inside the for loop, each character enters and leaves the window at most once.

O(n)

Space Complexity

The set stores only unique characters currently in the window.

O(min(n, charset))

or simply

O(n)

Brute Force vs Sliding Window

Approach

Time

Space

Brute Force

O(n²)

O(n)

Sliding Window

O(n)

O(n)

The sliding window solution avoids reprocessing characters, making it much more efficient for longer strings.

Key Takeaways

  • A set is perfect for checking duplicates in constant time.
  • The brute-force solution checks every possible substring but repeats a lot of work.
  • The sliding window technique maintains a valid substring by expanding to the right and shrinking from the left only when necessary.
  • Since every character is processed at most twice (once when added and once when removed), the optimal solution runs in O(n) time.

Sliding Window is one of the most important techniques for string and array problems, and mastering this pattern will help solve many interview questions efficiently.