Sliding Window maintains a contiguous substring between two pointers, with a frequency map enforcing the constraint.
Focus on recognizing:
“Longest/shortest substring” + “constraint” → expand right, shrink left
Pattern 1: Longest Substring Without Repeating Characters
Watch the window slide over "abcabcbb" — on a duplicate, left jumps straight past the old occurrence. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Longest Substring Without Repeating Characters
Find the longest contiguous substring with all-unique characters. A window [left, right] slides right; when a duplicate appears, left jumps past its last occurrence so the window always holds distinct characters.
Input: a b c a b c b b. The L/R pointers are the window. Grow right while every char is new; on a repeat, shrink left past the previous copy. Track the best window length. Watch the window shrink the moment a letter repeats, then grow again — best stays 3 ("abc").
1
for right in 0..n-1:
2
if s[right] seen inside window:
3
move left past its last occurrence
4
record last index of s[right]
5
best = max(best, right - left + 1)
public int lengthOfLongestSubstring(String s) {
int[] last = new int[128];
Arrays.fill(last, -1);
int best = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (last[c] >= left) { // duplicate inside window
left = last[c] + 1; // jump past it
}
last[c] = right;
best = Math.max(best, right - left + 1);
}
return best;
}def length_of_longest_substring(s):
last = {}
best = left = 0
for right, ch in enumerate(s):
if ch in last and last[ch] >= left:
left = last[ch] + 1 # jump past duplicate
last[ch] = right
best = max(best, right - left + 1)
return bestint lengthOfLongestSubstring(string s) {
vector<int> last(128, -1);
int best = 0, left = 0;
for (int right = 0; right < (int)s.size(); right++) {
char c = s[right];
if (last[c] >= left) // duplicate inside window
left = last[c] + 1; // jump past it
last[c] = right;
best = max(best, right - left + 1);
}
return best;
}function lengthOfLongestSubstring(s) {
const last = new Map();
let best = 0,
left = 0;
for (let right = 0; right < s.length; right++) {
const c = s[right];
if (last.has(c) && last.get(c) >= left)
left = last.get(c) + 1; // jump past duplicate
last.set(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}
leftonly ever jumps forward — each character enters and leaves the window once.
Store the last index of each character. On repeat, teleport
left— don’t inch it.
Pattern 2: At Most K Distinct Characters
Watch "eceba" with k=2 — the window grows until a third distinct char forces a shrink.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Longest Substring With At Most K Distinct
Like the no-repeat window, but the shrink rule changes: grow with R, and only shrink L while the window holds MORE than k distinct characters. Tracks a running distinct-count and best length.
String 'eceba', k=2. Grow until a 3rd distinct appears, then shrink L until back to ≤k distinct. Watch the highlighted window and the distinct counter in the state chip: it stays ≤2 and best length reaches 3 ('ece'). The 'too many distinct → shrink' rule is the only difference from the longest-unique window.
1
left = 0
2
for right from 0 to n-1:
3
add s[right] to window
4
while too many distinct chars:
5
remove s[left] from window
6
left = left + 1
7
best = longest window so far
8
return best
Frequency map + shrink while more than K distinct:
public int longestKDistinct(String s, int k) {
Map<Character, Integer> freq = new HashMap<>();
int best = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
freq.merge(c, 1, Integer::sum);
while (freq.size() > k) { // too many distinct
char out = s.charAt(left);
if (freq.merge(out, -1, Integer::sum) == 0)
freq.remove(out);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}from collections import defaultdict
def longest_k_distinct(s, k):
freq = defaultdict(int)
best = left = 0
for right, ch in enumerate(s):
freq[ch] += 1
while len(freq) > k: # too many distinct
out = s[left]
freq[out] -= 1
if freq[out] == 0:
del freq[out]
left += 1
best = max(best, right - left + 1)
return bestint longestKDistinct(string s, int k) {
unordered_map<char, int> freq;
int best = 0, left = 0;
for (int right = 0; right < (int)s.size(); right++) {
freq[s[right]]++;
while ((int)freq.size() > k) { // too many distinct
if (--freq[s[left]] == 0)
freq.erase(s[left]);
left++;
}
best = max(best, right - left + 1);
}
return best;
}function longestKDistinct(s, k) {
const freq = new Map();
let best = 0,
left = 0;
for (let right = 0; right < s.length; right++) {
const c = s[right];
freq.set(c, (freq.get(c) ?? 0) + 1);
while (freq.size > k) {
// too many distinct
const out = s[left];
const n = freq.get(out) - 1;
n === 0 ? freq.delete(out) : freq.set(out, n);
left++;
}
best = Math.max(best, right - left + 1);
}
return best;
}Delete zero-count entries — otherwise
freq.size()lies about distinct characters.
Pattern 3: Minimum Window Substring
Watch "ADOBECODEBANC" find "BANC" — expand right until valid, then shrink left while still valid.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Minimum Window Substring (Contains All of T)
Given S = "ADOBECODEBANC" and T = "ABC", find the shortest substring of S that contains at least one A, one B, and one C. The expected answer is "BANC", which has length 4.
Use a sliding window [left, right] and frequency counts for the target characters A, B, and C. For S = "ADOBECODEBANC" and T = "ABC", expand right until the window contains all three required characters. At right = 5, the window "ADOBEC" becomes valid with matched = 3. Save it, then shrink from the left one character at a time while it remains valid. Removing A makes the window invalid, so stop. Continue expanding. At right = 12, the window "ODEBANC" is valid again. Shrink it: removing O gives "DEBANC", removing D gives "EBANC", removing E gives "BANC", which is still valid and has length 4. Removing B would make the window invalid because no B remains, so stop. Therefore the minimum window is "BANC".
1
left = 0, matched = 0
2
for right from 0 to n-1:
3
add s[right] to window
4
if count matches target: matched = matched + 1
5
while all chars of t are matched:
6
if window is smaller than best: save it
7
remove s[left] from window
8
if removing breaks a match: matched = matched - 1
9
left = left + 1
10
return saved window
Opposite goal: shrink after the window becomes valid:
public String minWindow(String s, String t) {
int[] need = new int[128], have = new int[128];
for (char c : t.toCharArray()) need[c]++;
int missing = t.length(), left = 0;
int bestLen = Integer.MAX_VALUE, bestLeft = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (need[c] > have[c]) missing--; // one more covered
have[c]++;
while (missing == 0) { // valid → shrink
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestLeft = left;
}
char out = s.charAt(left++);
if (--have[out] < need[out]) missing++;
}
}
return bestLen == Integer.MAX_VALUE
? "" : s.substring(bestLeft, bestLeft + bestLen);
}from collections import Counter
def min_window(s, t):
need = Counter(t)
missing = len(t)
left = 0
best_len, best_left = float("inf"), 0
for right, ch in enumerate(s):
if need[ch] > 0:
missing -= 1 # one more covered
need[ch] -= 1
while missing == 0: # valid → shrink
if right - left + 1 < best_len:
best_len, best_left = right - left + 1, left
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
return "" if best_len == float("inf") \
else s[best_left:best_left + best_len]string minWindow(string s, string t) {
unordered_map<char, int> need;
for (char c : t) need[c]++;
int missing = t.size(), left = 0;
int bestLen = INT_MAX, bestLeft = 0;
for (int right = 0; right < (int)s.size(); right++) {
char c = s[right];
if (need[c] > 0) missing--; // one more covered
need[c]--;
while (missing == 0) { // valid → shrink
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestLeft = left;
}
need[s[left]]++;
if (need[s[left]] > 0) missing++;
left++;
}
}
return bestLen == INT_MAX ? "" : s.substr(bestLeft, bestLen);
}function minWindow(s, t) {
const need = new Map();
for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
let missing = t.length,
left = 0,
bestLen = Infinity,
bestLeft = 0;
for (let right = 0; right < s.length; right++) {
const c = s[right];
if (need.get(c) > 0) missing--; // one more covered
need.set(c, (need.get(c) ?? 0) - 1);
while (missing === 0) {
// valid → shrink
if (right - left + 1 < bestLen) {
bestLen = right - left + 1;
bestLeft = left;
}
const out = s[left++];
need.set(out, need.get(out) + 1);
if (need.get(out) > 0) missing++;
}
}
return bestLen === Infinity
? ""
: s.slice(bestLeft, bestLeft + bestLen);
}One
missingcounter replaces comparing two maps character-by-character.
Common Mistakes
Inching left one step per duplicate.
Store last indices and jump — O(n) total instead of O(n·k).
Keeping zero-count keys in the map.
freq.size() then overcounts distinct characters.
Shrinking before validity in minimum-window.
Expand until valid (missing == 0), THEN shrink to find the smallest valid window.
Complexity
| Variant | Time | Space |
|---|---|---|
| No-repeat substring | O(n) | O(min(n, alphabet)) |
| At most K distinct | O(n) | O(k) |
| Minimum window | O(n) | O(alphabet) |
Premium Content
Unlock Sliding Window and all premium lessons with a subscription.
From ₹199.99/year — See plans