Recognising the pattern
The brute-force approach checks every substring for uniqueness, which is O(n²) substrings times O(n) to verify, so O(n³), or O(n²) with an incremental set. The signal that a sliding window applies is that the property being tested is monotone under shrinking: if a window has no duplicates, every sub-window of it also has none. That means once a duplicate appears you never need to re-examine smaller windows starting at the same left boundary, so each pointer only ever moves forward.
The solution
The naive window advances left one position at a time until the duplicate is gone. That works and is still O(n) amortised, but the cleaner formulation stores the last index of each character and jumps left directly.
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastSeen = new HashMap<>();
int best = 0;
int left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
Integer previous = lastSeen.get(c);
if (previous != null) {
left = Math.max(left, previous + 1);
}
lastSeen.put(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}
The Math.max on the left pointer is where most candidates lose the point. Consider "abba". At right = 3 the character a was last seen at index 0, which is behind the current left of 2. Without the guard, left jumps back to 1 and the window becomes invalid, producing an answer of 3 instead of 2.
Complexity
Time is O(n): each index is visited once by right, and left only ever increases, so the total pointer movement is bounded by 2n. Space is O(min(n, k)) where k is the alphabet size, since the map holds at most one entry per distinct character.
If the interviewer constrains the input to ASCII, an int[128] array replaces the map and the space becomes O(1) by that assumption. State the assumption out loud rather than just writing the array — the substance of the point is knowing that O(1) here is a claim about the alphabet, not about the input length.
Cases to test
Walk these before the interviewer asks. The empty string returns 0. A single character returns 1. "bbbbb" returns 1 and exercises the immediate-duplicate path. "abba" returns 2 and is the one that catches the backwards-pointer bug. "pwwkew" returns 3 and confirms you are tracking the maximum across windows rather than returning the last window's length.
© 2026 Preptima. Originally published at preptima.com (opens in a new tab).