Longest run of distinct characters
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.
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))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.
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
Write a solution and run it against the real test table.
Keep going
Shortest subarray with a sum at least the target
A window that grows on the right until it qualifies, then shrinks on the left while it still does.
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.