Sliding Window — Longest Substring Without Repeating Characters
↗ LeetCode: Longest Substring Without Repeating Characters · Medium · pattern chapter →
Given a string s, return the length of the longest substring with all distinct characters.
Example 1 — s = "abcabcbb" → 3 (the substring "abc") Example 2 — s = "bbbbb" → 1Example 3 — s = "pwwkew" → 3 (the substring "wke"; note "pwke" is a subsequence, not a substring)
Constraints — 0 ≤ s.length ≤ 5·10⁴; ASCII / extended ASCII characters.
Interview timer00:00
Approach 1 — Brute force (all substrings, check distinct)
Intuition. Enumerate every substring s[i..j]; for each, verify all characters are distinct; track the max length.
int lengthOfLongestSubstringBrute(String s) {
int n = s.length(), best = 0;
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
if (allDistinct(s, i, j)) best = Math.max(best, j - i + 1);
}
}
return best;
}
boolean allDistinct(String s, int i, int j) {
Set<Character> seen = new HashSet<>();
for (int k = i; k <= j; k++) if (!seen.add(s.charAt(k))) return false;
return true;
}Complexity — Time O(n³) (O(n²) substrings × O(n) distinct check); Space O(min(n, alphabet)) per check.
At n=5·10⁴ this is ~10¹⁴ ops. TLE.
Approach 2 — Growing window with a set
Insight from brute. For a fixed left i, the maximal valid right j is monotonic in i. When we shrink i, the maximal j can only grow — never shrink. So we don't need to restart j from i each time.
Grow right while adding characters to a set. When a duplicate appears, shrink left (removing chars from the set) until the duplicate is gone.
int lengthOfLongestSubstringSet(String s) {
Set<Character> window = new HashSet<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
while (window.contains(c)) {
window.remove(s.charAt(left));
left++;
}
window.add(c);
best = Math.max(best, right - left + 1);
}
return best;
}Complexity — Time O(2n) = O(n) (each char enters and leaves once); Space O(min(n, alphabet)).
Big win. But shrinking left one-at-a-time is wasteful — we walk past chars we already know are gone.
Approach 3 — Last-seen index map (one pass)
Insight from set window. When the duplicate s[right] was last seen at position prev, we can jump left directly to prev + 1 in O(1) instead of walking. Store the last-seen index of every character.
Trap — clamp left to its current value: left = max(left, prev + 1). Otherwise left retreats on stale duplicates outside the current window.
int lengthOfLongestSubstring(String s) {
Map<Character, Integer> last = new HashMap<>();
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (last.containsKey(c)) {
left = Math.max(left, last.get(c) + 1);
}
last.put(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}Complexity — Time O(n) (single scan); Space O(min(n, alphabet)) for the map.
Optimal. One pass, O(1) work per index.
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Brute force | O(n³) | O(alphabet) | Baseline; TLE at n=5·10⁴ |
| Set-based window | O(n) | O(alphabet) | Correct, but shrinks step-by-step |
| Last-seen map | O(n) | O(alphabet) | Expected optimum |
When to use which
- First pass on a Sliding Window problem → state brute for signal, then jump to last-seen.
- Interviewer probes "why not shrink step-by-step?" → it works, but wastes O(n) traversal on stale duplicates.
- "Return the substring itself, not just length" → track the best
(start, length)pair. - "What if the alphabet is Unicode?" → HashMap works unchanged; a
char[128]array works for ASCII only.
Related problems (same ladder applies)
- Minimum Window Substring — same window skeleton,
need/havecounter for the validity check - Longest Substring with At Most K Distinct — validity:
distinct ≤ k - Longest Repeating Character Replacement — window is valid if
(windowLen − maxFreq) ≤ k - Permutation in String — fixed-size window, count-match