These are the notes for DSA episode 9, where we meet the sliding window, one of the most used patterns in coding interviews. The problem (LeetCode 3) asks for the longest piece of a string with no repeated character. The brute force checks every piece and times out; the sliding window keeps one clean piece and slides it along the string in a single O(n) pass. Then we make it jump instead of crawl, and fix the two bugs that catch most people. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
On a long overnight bus ride, the driver's playlist plays non-stop, one song after another, and the same hit keeps coming back. What was the longest stretch of songs played back to back in which no song came twice? Write each song as a letter, and that is exactly this problem.
Problem statement
Given a string s, return the length of the longest substring without repeating characters. Constraints: 0 ≤ s.length ≤ 5 × 10⁴; s has English letters, digits, symbols and spaces.
| s | answer | one longest substring |
|---|---|---|
"abcabcbb" |
3 | "abc" |
"bbbbb" |
1 | "b" |
"pwwkew" |
3 | "wke" |
"" |
0 | (none) |
"aaaa" |
1 | "a" |
"abcdef" |
6 | "abcdef" |
"dvdf" |
3 | "vdf" |
Substring vs subsequence
A substring is one continuous, back-to-back piece of the string. A subsequence keeps the order but may skip characters. In "pwwkew", "wke" is a substring; "pwke" is only a subsequence (it skips the second w), so it does not count.
Solution 1: brute force (check every substring)
Try every start i and every end j, and check whether s[i..j] has all different characters with a boolean[128] (one slot per ASCII character).
public class Main {
static boolean unique(String s, int i, int j) {
boolean[] seen = new boolean[128];
for (int k = i; k <= j; k++) {
if (seen[s.charAt(k)]) return false;
seen[s.charAt(k)] = true;
}
return true;
}
static int longest(String s) {
int best = 0;
for (int i = 0; i < s.length(); i++)
for (int j = i; j < s.length(); j++)
if (unique(s, i, j)) best = Math.max(best, j - i + 1);
return best;
}
public static void main(String[] args) {
System.out.println(longest("abcabcbb"));
System.out.println(longest("bbbbb"));
System.out.println(longest("pwwkew"));
}
}
Output:
3
1
3
Correct. Now one lakh characters (the alphabet repeated, built with (char) ('a' + i * 7 % 26), answer 26):
int n = 100000;
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.append((char) ('a' + i * 7 % 26));
System.out.println(longest(sb.toString()));
Result: Time Limit Exceeded (more than 8 seconds).
Why it is slow, and the fix
- A string of n characters has about n²/2 substrings: 5 billion for n = 10⁵.
- Each one is checked from scratch (a fresh array every time), so the worst case is O(n³).
- The waste: once we know
"abc"is clean, checking"abca"re-checksa,b,cagain. The only new question is about the new character: is it already inside the piece we hold?
So keep the clean piece, called a window, and only ask about the new character.
Solution 2: the sliding window with a HashSet
- The window is
s[left..right], and it is always repeat-free. - Grow: move
rightone step and look at the new characterc. - Shrink: while
cis already in the window, removes[left]and moveleftforward. - Add
c; the window lengthright - left + 1is a candidate for the answer. - A HashSet remembers what is inside the window;
contains,addandremoveare O(1) on average.
| Bus playlist | Code |
|---|---|
| The current clean stretch of songs | the window s[left..right] |
| The next song plays | right++ (grow) |
| A checklist of songs in the stretch | HashSet<Character> window |
| A repeat: drop the oldest songs until the old copy is gone | window.remove(s.charAt(left)); left++ (shrink) |
Dry run: "abcabcbb"
| right | char | action | window | best |
|---|---|---|---|---|
| 0 | a | add | a | 1 |
| 1 | b | add | ab | 2 |
| 2 | c | add | abc | 3 |
| 3 | a | a inside: remove a, left = 1; add |
bca | 3 |
| 4 | b | b inside: remove b, left = 2; add |
cab | 3 |
| 5 | c | c inside: remove c, left = 3; add |
abc | 3 |
| 6 | b | remove a, b (left = 5); add |
cb | 3 |
| 7 | b | remove c, b (left = 7); add |
b | 3 |
Answer: 3.
import java.util.*;
public class Main {
static int longest(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;
}
public static void main(String[] args) {
System.out.println(longest("abcabcbb"));
System.out.println(longest("bbbbb"));
System.out.println(longest("pwwkew"));
System.out.println(longest(""));
System.out.println(longest("aaaa"));
System.out.println(longest("abcdef"));
System.out.println(longest("dvdf"));
}
}
Output:
3
1
3
0
1
6
3
On ten lakh characters (same generator, n = 1000000, timed with System.nanoTime()):
26 124 ms
Why is it O(n) when there is a loop inside a loop? right moves n times. left only ever moves forward, so across the whole run it moves at most n times. Every character is added once and removed at most once: at most 2n set operations.
Solution 3: jump with the last-seen index
Shrinking one step at a time is unnecessary. When c repeats, the only thing we need is where c was seen last; left can jump straight to last[c] + 1.
int[] last = new int[128], filled with-1(not seen yet).- For each
right:left = Math.max(left, last[c] + 1), thenlast[c] = right. - The
Math.maxmatters: an old copy ofcmay already be behind the window (see the abba bug below).
Dry run: "abba"
| right | char | last[c] before | left | window | best |
|---|---|---|---|---|---|
| 0 | a | -1 | max(0, 0) = 0 | a | 1 |
| 1 | b | -1 | max(0, 0) = 0 | ab | 2 |
| 2 | b | 1 | max(0, 2) = 2 | b | 2 |
| 3 | a | 0 | max(2, 1) = 2 | ba | 2 |
Without the max, row 3 would set left = 1 and count "bba" (length 3), which has a repeat.
import java.util.*;
public class Main {
static int longest(String s) {
int[] last = new int[128];
Arrays.fill(last, -1);
int left = 0, best = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
left = Math.max(left, last[c] + 1);
last[c] = right;
best = Math.max(best, right - left + 1);
}
return best;
}
public static void main(String[] args) {
System.out.println(longest("abcabcbb"));
System.out.println(longest("abba"));
}
}
Output:
3
2
On ten lakh characters:
26 20 ms
The same solution in C++ and Python
C++ (unsigned char so that bytes above 127 never give a negative index; 256 slots cover every byte):
#include <bits/stdc++.h>
using namespace std;
int longestSet(const string& s) {
unordered_set<char> window;
int left = 0, best = 0;
for (int right = 0; right < (int)s.size(); right++) {
char c = s[right];
while (window.count(c)) window.erase(s[left++]);
window.insert(c);
best = max(best, right - left + 1);
}
return best;
}
int longest(const string& s) {
vector<int> last(256, -1);
int left = 0, best = 0;
for (int right = 0; right < (int)s.size(); right++) {
unsigned char c = s[right];
left = max(left, last[c] + 1);
last[c] = right;
best = max(best, right - left + 1);
}
return best;
}
int main() {
for (string s : {"abcabcbb", "bbbbb", "pwwkew", "", "aaaa", "abcdef", "dvdf", "abba", "tmmzuxt"})
cout << longestSet(s) << " " << longest(s) << "\n";
}
Output:
3 3
1 1
3 3
0 0
1 1
6 6
3 3
2 2
5 5
Python (a dict handles any character, so there is no 128-slot problem):
def longest_set(s: str) -> int:
window = set()
left = best = 0
for right, c in enumerate(s):
while c in window:
window.remove(s[left])
left += 1
window.add(c)
best = max(best, right - left + 1)
return best
def longest(s: str) -> int:
last = {}
left = best = 0
for right, c in enumerate(s):
if c in last:
left = max(left, last[c] + 1)
last[c] = right
best = max(best, right - left + 1)
return best
for s in ["abcabcbb", "bbbbb", "pwwkew", "", "aaaa", "abcdef", "dvdf", "abba", "tmmzuxt", "café au lait"]:
print(longest_set(s), longest(s))
Output:
3 3
1 1
3 3
0 0
1 1
6 6
3 3
2 2
5 5
6 6
The abba bug (left moves backwards)
The "natural" jump without Math.max:
if (last[c] != -1) left = last[c] + 1;
Output for "abcabcbb" and "abba":
3
3
"abba" should be 2. No error and no crash, just a wrong answer: at the last a, left jumps back from 2 to 1 because the old a (index 0) is already outside the window. Fix: left = Math.max(left, last[c] + 1);.
The café crash (non-ASCII characters)
With int[] last = new int[128], the input "café au lait" crashes:
3
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 233 out of bounds for length 128
at Main.longest(Main.java:10)
at Main.main(Main.java:18)
é is character 233, past the last slot (127). Fixes: new int[65536] (one slot per Java char), which prints 6 for "café au lait", or a HashMap<Character, Integer>. In an interview, ask which characters can appear.
Complexity
| Approach | Time | Extra space | n = 10⁶ |
|---|---|---|---|
| Brute force (check every substring) | O(n³) worst case | O(k) per check | Time Limit Exceeded (already at n = 10⁵) |
| Sliding window + HashSet | O(n) | O(k) | 124 ms |
| Sliding window + last-seen index | O(n) | O(k) | 20 ms |
k is the number of possible characters (128 for ASCII), so the space is often called O(1).
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
left = last[c] + 1 (no max) |
"abba" → 3 (answer is 2) |
the old copy is behind the window, so left jumps backwards | left = Math.max(left, last[c] + 1) |
int[] last = new int[128] on "café" |
ArrayIndexOutOfBoundsException: Index 233 out of bounds for length 128 |
é is char 233 |
new int[65536] or a HashMap |
if (window.contains(c)) remove once |
the window keeps a repeat, the answer is too big | the old copy may be further left than one step | while, not if |
best = right - left |
every answer one too small | both ends are inside the window | right - left + 1 |
Counting a subsequence ("pwke") |
4 for "pwwkew" |
a substring must be back to back | only contiguous windows |
Mini project: playlist report
Read a playlist as a line of song codes (one letter per song, e.g. abcabdeafb). Print the longest stretch with no repeated song and the songs in it, plus how many times the window had to shrink. Hint: track bestStart whenever best improves, then print s.substring(bestStart, bestStart + best).
Practice
- Return the longest substring itself, not just its length.
Solution
Whenever right - left + 1 > best, also save bestStart = left. Return s.substring(bestStart, bestStart + best). Results: "pwwkew" → "wke", "abcabcbb" → "abc", "tmmzuxt" → "mzuxt".
- Longest substring with at most two distinct characters (LeetCode 159).
Solution
Same window, different rule: keep a count of each character in the window; grow right, and while the window has more than 2 distinct characters, decrease the count of s[left] (remove it at 0) and move left. "eceba" → 3 ("ece"), "ccaabbb" → 5 ("aabbb"). O(n).
- Longest repeating character replacement (LeetCode 424): you may change up to
kcharacters.
Solution
A window is valid when length - (count of its most frequent char) ≤ k. Grow right, update the max count, and shrink left while the window is invalid. "AABABBA", k = 1 → 4; "ABAB", k = 2 → 4.
- Why is the set version O(n) even though it has a
whileinside afor?
Solution
left only moves forward and never past right, so the inner loop runs at most n times in total over the whole run, not n times per character.
Quick quiz
What does longest("tmmzuxt") return?
- 5
- 4
- 6
- 7
Answer
5 ("mzuxt"). At the second m the window shrinks past the first m (and the first t). Then m, z, u, x, t grows to 5. The last t repeats the first t, but that one is already outside the window.
Interview questions
- What is a sliding window? Two indexes
left ≤ rightthat both move only forward, keeping a piece of the array or string that satisfies a rule; grow on the right, shrink on the left when the rule breaks. - Why is it O(n)? Each index moves at most n times, so the total work is at most 2n steps.
- Set version vs last-index version? Both O(n); the last-index version does one step per character instead of removing characters one by one.
- Why
Math.max(left, last[c] + 1)? The last copy ofcmay be beforeleft(already outside the window); without max, left moves backwards ("abba"→ 3). - What if the input is Unicode? A 128-slot array crashes on characters above 127; use a
HashMap, or 65536 slots for Javachars.
Glossary
| Term | Meaning |
|---|---|
| String | A sequence of characters, like "abcabcbb" |
| Substring | One continuous, back-to-back piece of a string: "wke" in "pwwkew" |
| Subsequence | Characters in order, possibly skipping some: "pwke" in "pwwkew" |
| Repeating character | A character that appears more than once in the piece |
| Brute force | Trying every possibility directly, without reusing earlier work |
| Sliding window | A piece s[left..right] that grows on the right and shrinks on the left, both ends only moving forward |
| Window length | right - left + 1 (both ends included) |
| HashSet | A Java collection of unique items with O(1) average contains, add and remove |
| Last-seen index | For each character, the most recent index where it appeared (last[c]) |
| ASCII | The first 128 character codes (English letters, digits, common symbols) |
ArrayIndexOutOfBoundsException |
Java's error when an index is below 0 or not less than the array's length |
Unicode / char |
Java stores text as 16-bit chars (0 to 65535); é is 233 |
| Amortized O(n) | The total work over the whole run is O(n), even if one step sometimes does more |
Summary
- A substring is one back-to-back piece; checking every substring is O(n²) pieces and times out.
- The sliding window keeps a repeat-free piece: grow on the right, shrink on the left; a HashSet remembers what is inside. O(n).
- Jump version:
left = Math.max(left, last[c] + 1), one step per character. leftmust never move backwards (the abba bug), and 128 slots only work for ASCII (the café crash).
Next episode: Minimum Window Substring (hard).