Longest Substring Without Repeating Characters

If you are learning Data Structures and Algorithms (DSA), you will almost certainly come across the problem —
Longest Substring Without Repeating Characters. It is one of the most popular problems
asked in coding interviews at companies like Google, Amazon, Microsoft, and many others.

At first, this problem might sound confusing. But once you understand the idea of a
sliding window, it becomes very straightforward. This guide will walk you through
everything — what the problem is, how to think about it, how to write clean Python code,
and what to expect in an interview.

What does “substring” mean?

A substring is a continuous sequence of characters within a string.
For example, in the string "abcde", the substrings include
"abc", "bcd", "de", and so on.
A single character like "a" is also a valid substring.

What does “without repeating characters” mean?

It means every character in the substring appears only once.
For example, "abc" has no repeating characters, but "abca"
has 'a' repeating — so it is not valid.

Let’s Understand with an Example

Take the string: "abcabcbb"

• Starting from index 0: "abc" → all unique → length 3 ✅
• Continue: "abca" → 'a' repeats → stop
• Slide the window: "bca" → all unique → length 3 ✅
• Continue sliding… the longest we find is still 3

So the answer is 3.

Let’s break down exactly how the code works, step by step.
We’ll trace through the string "abcabcbb" to see it in action.

Step 1 — Setting Up

We create a set called char_set.
A set is a collection that stores unique items and lets us check if something is inside it
in constant time O(1).

We also create two variables: left = 0 (start of our window) and
max_len = 0 (best answer so far).

Step 2 — Expanding the Window

The right pointer moves from the beginning of the string to the end,
one character at a time.
At each step, we check if s[right] is already in our set.

• If it is NOT in the set → we add it and expand the window.
• If it IS in the set → we shrink from the left until the duplicate is removed.

Step 3 — Shrinking the Window

When a repeat is found, we remove s[left] from the set and
move left one step to the right.
We keep doing this until the duplicate character is gone.

Step 4 — Updating the Answer

After each valid addition, the window size is right - left + 1.
We compare this with our current max_len and keep the larger value.

Dry Run on “abcabcbb”

String:  a  b  c  a  b  c  b  b
Index:   0  1  2  3  4  5  6  7

right=0: s[0]='a' not in {} → add → set={'a'}  → window="a"   → max_len=1
right=1: s[1]='b' not in {'a'} → add → set={'a','b'} → window="ab" → max_len=2
right=2: s[2]='c' not in {'a','b'} → add → set={'a','b','c'} → max_len=3
right=3: s[3]='a' IS in set →
         remove s[0]='a', left=1 → set={'b','c'}
         now add 'a' → set={'b','c','a'} → window="bca" → max_len=3
right=4: s[4]='b' IS in set →
         remove s[1]='b', left=2 → set={'c','a'}
         add 'b' → window="cab" → max_len=3
right=5: s[5]='c' IS in set →
         remove s[2]='c', left=3 → set={'a','b'}
         add 'c' → window="abc" → max_len=3
right=6: s[6]='b' IS in set →
         remove s[3]='a', left=4 → set={'b','c'}
         'b' still in set, remove s[4]='b', left=5 → set={'c'}
         add 'b' → window="cb" → max_len=3
right=7: s[7]='b' IS in set →
         remove s[5]='c', left=6 → set={'b'}
         'b' still in set, remove s[6]='b', left=7 → set={}
         add 'b' → window="b" → max_len=3

Final answer: 3