Longest run of distinct characters
Medium · Target 15 minutes · Sliding window· Type asked at
Optiver
Google
Deutsche Bank
Given a string s, return the length of the longest contiguous substring in
which no character repeats.
Examples
| Input | Output | Why |
|---|---|---|
s = "abcabcbb" | 3 | "abc". |
s = "bbbbb" | 1 | "b". |
s = "pwwkew" | 3 | "wke". "pwke" is a subsequence, not a substring. |
Constraints
- 0 ≤ |s| ≤ 10⁵
- s contains printable ASCII characters
Hints
Hint 1
Brute force checks every substring in O(n²) or worse. What work is being repeated?
Hint 2
Keep a window that is always valid — no repeats inside it — and never move the left edge backwards.
Hint 3
When you meet a character you have seen inside the current window, jump the left edge to just past its previous position. Store the last index of each character.
Where people lose marks
- Moving the left edge back when an old duplicate appears outside the window. Take
max(lo, prev + 1). - Forgetting the empty string, which must return 0.
- Clearing the whole map on a violation. That turns the scan quadratic; only the left edge needs to move.
Dry run on "tmmzuxt"
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 7st0lo/him1m2z3u4x5t6best1window1
't' is new to the window. It grows to length 1; best so far 1.
-
Step 2 / 7st0lom1him2z3u4x5t6best2window2
'm' is new to the window. It grows to length 2; best so far 2.
-
Step 3 / 7st0m1m2lo/hiz3u4x5t6best2window1
'm' is already inside the window, last seen at 2. Jump lo to 2; the window is valid again and now length 1.
-
Step 4 / 7st0m1m2loz3hiu4x5t6best2window2
'z' is new to the window. It grows to length 2; best so far 2.
-
Step 5 / 7st0m1m2loz3u4hix5t6best3window3
'u' is new to the window. It grows to length 3; best so far 3.
-
Step 6 / 7st0m1m2loz3u4x5hit6best4window4
'x' is new to the window. It grows to length 4; best so far 4.
-
Step 7 / 7st0m1m2loz3u4x5t6hibest5window5
't' is new to the window. It grows to length 5; best so far 5.
How to think about it
Hold a window [lo, hi] that always satisfies the property you want: every
character inside it is distinct. Extend hi one character at a time. If the new
character already sits inside the window, the window is no longer valid, and the only repair that
keeps hi is to move lo to just past the earlier copy.
Because lo never moves left, each pointer travels the length of the string once:
the whole scan is linear even though the window changes size constantly. A map from character to
last index seen makes the jump O(1); with a fixed alphabet an array of 128 integers is
faster than a hash map and worth mentioning in an interview.
The same skeleton — extend, detect violation, shrink from the left, record the best — solves "at most k distinct", "longest with at most one replacement" and most of the window family. What changes is only the test for a violation.
Complexity. Time O(n) · Space O(min(n, alphabet))
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def longest_unique(s):
last = {} # character -> last index where it was seen
best = lo = 0
for hi, ch in enumerate(s):
if ch in last and last[ch] >= lo:
lo = last[ch] + 1 # jump past the earlier copy; never move left
last[ch] = hi
best = max(best, hi - lo + 1)
return best#include <string>
#include <array>
#include <algorithm>
int solve(const std::string& s) {
std::array<int, 128> last{};
last.fill(-1); // fixed alphabet beats a hash map here
int best = 0, lo = 0;
for (int hi = 0; hi < static_cast<int>(s.size()); ++hi) {
unsigned char ch = static_cast<unsigned char>(s[hi]);
if (last[ch] >= lo) lo = last[ch] + 1;
last[ch] = hi;
best = std::max(best, hi - lo + 1);
}
return best;
}class Solution {
public int longestUnique(String s) {
int[] last = new int[128];
java.util.Arrays.fill(last, -1);
int best = 0, lo = 0;
for (int hi = 0; hi < s.length(); hi++) {
char ch = s.charAt(hi);
if (last[ch] >= lo) lo = last[ch] + 1;
last[ch] = hi;
best = Math.max(best, hi - lo + 1);
}
return best;
}
}function longestUnique(s) {
const last = new Map(); // character -> last index seen
let best = 0, lo = 0;
for (let hi = 0; hi < s.length; hi++) {
const ch = s[hi];
if (last.has(ch) && last.get(ch) >= lo) lo = last.get(ch) + 1;
last.set(ch, hi);
best = Math.max(best, hi - lo + 1);
}
return best;
}fn solve(s: &str) -> usize {
let mut last = [usize::MAX; 128]; // MAX stands for "not seen"
let (mut best, mut lo) = (0usize, 0usize);
for (hi, ch) in s.bytes().enumerate() {
let seen = last[ch as usize];
if seen != usize::MAX && seen >= lo {
lo = seen + 1;
}
last[ch as usize] = hi;
best = best.max(hi - lo + 1);
}
best
}import qualified Data.Map.Strict as M
-- Fold across the string carrying (last-seen map, window start, best so far).
solve :: String -> Int
solve s = best
where
(_, _, best) = foldl step (M.empty, 0, 0) (zip [0 ..] s)
step (seen, lo, acc) (hi, ch) =
let lo' = case M.lookup ch seen of
Just p | p >= lo -> p + 1
_ -> lo
seen' = M.insert ch hi seen
in (seen', lo', max acc (hi - lo' + 1))Variants to try
- At most k distinct characters instead of all distinct: keep counts and shrink while the map is too large.
- Return the substring rather than the length: remember where the best window started.
- Streaming input, where you cannot store the string: the same state works, since only last-seen indices matter.
Next problems
Longest run of tasks within a time budget
With positive numbers, a run that is over budget only gets worse as it grows, so the left end never moves back.
Open the problem → Medium20 minLongest run with at most k distinct letters
The variable window in its plainest form: grow on the right, and while the window breaks the rule, shrink on the left.
Open the problem → Medium15 minLongest run of ones after k flips
Rephrase "flip at most k zeros" as "a window with at most k zeros", and a counter is all the state you need.
Open the problem →Write a solution and run it against the real test table.
Keep going
Longest run of tasks within a time budget
With positive numbers, a run that is over budget only gets worse as it grows, so the left end never moves back.
Open the problem → Medium20 minLongest run with at most k distinct letters
The variable window in its plainest form: grow on the right, and while the window breaks the rule, shrink on the left.
Open the problem → Medium15 minLongest run of ones after k flips
Rephrase "flip at most k zeros" as "a window with at most k zeros", and a counter is all the state you need.
Open the problem → Sliding windowThe pattern behind it
A window that grows on the right, shrinks on the left, and holds an invariant at all times.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.