IntermediateStringsHashing
Longest Substring Without Repeating Characters
Problem
Given a string s, return the length of the longest substring that contains no repeated characters. A substring is contiguous; characters are compared exactly (case-sensitive).
Constraints
- 0 ≤ s.length ≤ 5·10^4
- s consists of printable ASCII characters (or Unicode — clarify)
Examples
in: s = "abcabcbb"
out: 3
"abc" is the longest substring with all distinct characters.
in: s = "pwwkew"
out: 3
"wke". Note "pwke" is a subsequence, not a substring.
What this tests
- Variable-size sliding window driven by a "no duplicates" invariant
- Choosing between a frequency map and a last-seen-index map
- Handling the window jump correctly (never move
leftbackwards) - Distinguishing substring from subsequence
Pattern RecognitionOptimizationImplementationEdge CasesComplexity Analysis
Progressive hints
Choose how much help you want. Each hint reveals a little more; the pattern is not named until hint 2.
Hint 1Direction
Hint 2Pattern
Hint 3Data structure
Hint 4Algorithm
Hint 5Pseudocode
Solution
Solve in your language
The editor, starter code and solution adapt to the language you pick — C++, JavaScript, TypeScript or Python.
Solve in
Candidate thinking
How a strong candidate reasons through this problem, step by step.
Try the problem yourself first (or run the mock interview), then compare your process against a strong candidate's.
Follow-up engine
Requirements change; so does the right algorithm.
F1
Return the substring itself, not just the length.
F2
Longest substring with at most
k distinct characters.F3
Longest substring where each character appears at most
m times.F4
The string is a stream and you need the answer after every character.