What is the brute force approach and complexity for Longest Substring Without Repeating Characters?

For each start, extend right with a fresh 'seen' table until a repeat with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Longest Substring Without Repeating Characters?

Remember where each character was last seen; jump left past it in one step with optimal time complexity O(N) and space complexity O(min(N, C)).

Longest Substring Without Repeating Characters

Q: How do you identify the pattern for Longest Substring Without Repeating Characters?

Look for key signals in the prompt: "substring" indicates Contiguous range [left … right] → think window.; "longest" indicates The window size is the answer → variable window. Longest → shrink while invalid, record after fixing.; "without repeating characters" indicates The rule is about what is inside the window → keep a set, count array, or last-seen index..

Medium·LeetCode #3 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given a string s.

Find the length of the longest substring in which no character appears more than once.

A substring is a contiguous piece of the string. "wke" is a substring of "pwwkew", but "pwke" is not (its letters are not next to each other).

Input

A string s.

Output

The length of the longest substring with all characters different.

Example 1

Input: s = "abcabcbb"

Output: 3

"abc" has no repeats and has length 3. Any longer piece repeats a letter.

Example 2

Input: s = "bbbbb"

Output: 1

Every piece longer than 1 has two b's. The best is "b".

Example 3

Input: s = "pwwkew"

Output: 3

"wke" works. "pwke" would be longer, but it is not contiguous, so it doesn't count.

Constraints

• 0 ≤ s.length ≤ 5 · 10^4
• s contains English letters, digits, symbols and spaces
• The string can be empty — the answer is then 0.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“substring”

→ Contiguous range [left … right] → think window.

“longest”

→ The window size is the answer → variable window. Longest → shrink while invalid, record after fixing.

“without repeating characters”

→ The rule is about what is inside the window → keep a set, count array, or last-seen index.

Approach Complexity Ladder

Brute Force — try every startO(N²)O(1)

For each start, extend right with a fresh 'seen' table until a repeat

Better — sliding window with a setO(N)O(min(N, C))

Grow right; while s[right] is already in the set, remove s[left] and move left

Optimal — sliding window with last-seen indexO(N)O(min(N, C))

Remember where each character was last seen; jump left past it in one step

Brute Force Intuition

For every start position, walk right and mark each character as seen. As soon as a character is already marked, this start can't go further — stop and move to the next start. The longest clean stretch over all starts is the answer.

Recognition rule for this sub-pattern:

Window grows and shrinks. Expand right; when the window breaks the rule, move left until it is valid again. Works when "bigger window = harder to be valid".

Remember this · Sliding Window

Trigger

Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".

Think

Can I keep a valid range and move it, instead of checking every subarray from scratch?

Key question

When is my current window valid?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Subarray with Given Sum (non-negative numbers)Max Consecutive Ones III