Part 7 · Lesson 31 · read

Substrings and Windows

Use a sliding window on text: no repeated letters, replacing characters, anagrams and the smallest window.

A window is two markers and a little memory
The variable-window template
Longest substring without repeating characters
Traced: windows over “abcabcbb”
Longest repeating character replacement
Fixed-size windows: permutations and anagrams
Minimum window substring
Practice questions (7)
Make it stick
Part 7 complete: what's next

A window is two markers and a little memory

Lessons 22 and 23 taught the sliding window on arrays. On text it is the same idea. Think of a small frame that you slide along a line of letters. Two pointers (markers), left and right, mark the two ends of a substring (a piece of the text with no gaps). A little memory tells you what is inside the frame right now. It can be a Set (a collection that keeps each item only once), a Map (a collection of key and value pairs, such as letter and count) or an array of counts. Moving the window one step costs O(1), which means it takes the same short time however long the text is. You only update the one letter that enters or leaves. You do not count the whole substring again.

The brute-force way is to check every substring. There are O(n²) substrings and each check costs O(n), so the total is O(n³). The window turns this into one O(n) pass (the time grows in step with the text length, so double the text means double the work). Each pointer only moves forward, so together they move at most 2n times.

Two kinds of windows cover almost every question.

Variable-size windows grow and shrink to stay valid. The question sounds like “find the longest substring where…”.
Fixed-size windows always have the same length and just slide. The question sounds like “is any window of length k an anagram of…”. (An anagram uses the same letters in a different order.)

The variable-window template

JavaScript

// Variable-size window: grow on the right, shrink from the left while the window is not valid.let left = 0;for (let right = 0; right < s.length; right++) {  // 1. add s[right] to what the window remembers (a Set, counts, ...)  while (/* the window is not valid */) {    // 2. remove s[left] from what the window remembers    left++;  }  // 3. the window s[left..right] is valid now: save the answer (length, start, ...)}

Every problem needs three decisions: what the window remembers, when the window is not valid and what to save when the window is valid. Once you can answer these three, the code is easy to write.

Longest vs shortest

For a longest valid window, save the answer after the shrinking, because the window is valid at that point. For a shortest valid window (minimum window substring), save the answer inside the shrink loop, while the window is still valid. Then shrink more to see if it can get even smaller.

Longest substring without repeating characters

Memory: a Set (a collection that keeps each item only once) of the letters in the window.
Not valid: the new letter is already in the Set.
Shrink: remove letters from the left until the repeat is gone.
Save: the length right - left + 1 after adding the new letter.

JavaScript

function lengthOfLongestSubstring(s) {  const seen = new Set();            // letters that are inside the window now  let left = 0, best = 0;  for (let right = 0; right < s.length; right++) {    while (seen.has(s[right])) {     // s[right] is a repeat: shrink until it is gone      seen.delete(s[left]);      left++;    }    seen.add(s[right]);    best = Math.max(best, right - left + 1);  }  return best;}console.log(lengthOfLongestSubstring("abcabcbb")); // 3console.log(lengthOfLongestSubstring("bbbbb"));    // 1console.log(lengthOfLongestSubstring("pwwkew"));   // 3console.log(lengthOfLongestSubstring(""));         // 0

Each letter is added once and removed at most once, so the time is O(n). The Set can never hold more than the number of different letters in the text or in the alphabet, so the space is O(min(n, alphabet)). That means it is the smaller of the text length and the alphabet size.

Traced: windows over “abcabcbb”

step 1 / 24

Set up

left = 0, best = 0

The window s[left..right] starts empty. The Set will hold exactly the letters that are inside the window.

1const s = "abcabcbb";2const seen = new Set();▶let left = 0, best = 0;4for (let right = 0; right < s.length; right++) {5  while (seen.has(s[right])) {6    seen.delete(s[left]);7    left++;8  }9  seen.add(s[right]);10  best = Math.max(best, right - left + 1);11}12console.log(best);

Variables

s	"abcabcbb"
left	0
best	0
seen	Set(0) {}

Console

(nothing printed yet)

The window grows while the letters are new. It shrinks from the left only when a repeated letter arrives. · interactive

Dry run · "pwwkew"

right	char	repeat?	window after	best
0	p	no	p	1
1	w	no	pw	2
2	w	yes → drop p, w	w	2
3	k	no	wk	2
4	e	no	wke	3
5	w	yes → drop w	kew	3

The answer is 3 (“wke” or “kew”). “pwke” does not count. It skips a letter, so it is a subsequence (letters in the same order, but gaps are allowed) and not a substring. A window must have no gaps.

Longest repeating character replacement

You may change up to k letters. You want the longest window that can become one repeated letter. That is the longest window where (window size − count of the most common letter) ≤ k. The letters that are not the most common one are the ones you would change.

JavaScript

function characterReplacement(s, k) {  const count = {};  let left = 0, maxFreq = 0, best = 0;  for (let right = 0; right < s.length; right++) {    count[s[right]] = (count[s[right]] || 0) + 1;    maxFreq = Math.max(maxFreq, count[s[right]]);        // highest count of one letter seen in any window so far    // letters to change = window size - count of the most common letter    while (right - left + 1 - maxFreq > k) {      count[s[left]]--;      left++;    }    best = Math.max(best, right - left + 1);  }  return best;}console.log(characterReplacement("ABAB", 2));    // 4console.log(characterReplacement("AABABBA", 1)); // 4

Why maxFreq can be out of date, and why that is fine

When the window shrinks, we do not work out maxFreq again. So it can be bigger than the real highest count inside the window. This is safe. The answer can only get bigger when a window with a larger maxFreq appears. An out-of-date value never lets the window grow past a size we already reached. It also saves us from checking all 26 counters at every step.

Fixed-size windows: permutations and anagrams

An anagram of p has exactly the same letter counts as p and the same length. So slide a window of length p.length across s. Keep its letter counts up to date: add the letter that enters and subtract the letter that leaves. Then compare with the counts of p.

JavaScript

function findAnagrams(s, p) {  const idx = (c) => c.charCodeAt(0) - 97;  const need = new Array(26).fill(0);            // letter counts of p  const win = new Array(26).fill(0);             // letter counts of the window now  for (const c of p) need[idx(c)]++;  const result = [];  for (let i = 0; i < s.length; i++) {    win[idx(s[i])]++;                            // letter enters on the right    if (i >= p.length) win[idx(s[i - p.length])]--;   // letter leaves on the left: the window stays p.length long    if (i >= p.length - 1 && need.every((n, j) => n === win[j])) {      result.push(i - p.length + 1);             // start index of this anagram    }  }  return result;}console.log(findAnagrams("cbaebabacd", "abc")); // [0, 6]console.log(findAnagrams("abab", "ab"));        // [0, 1, 2]

Comparing two arrays of 26 numbers costs O(26). That is a fixed amount, so it does not grow with the text, and the total time is O(n). The “permutation in string” question below uses the same loop. It just returns true at the first match.

Minimum window substring

Find the smallest substring of s that contains every letter of t, with the right counts. The window is valid when no letter is missing. This is the “shortest” kind. Grow the window until it has all of t. Then shrink it as far as you can while it still has all of t. Save the best window each time.

JavaScript

function minWindow(s, t) {  const need = new Map();                        // how many of each letter we still need  for (const c of t) need.set(c, (need.get(c) || 0) + 1);  let missing = t.length;                        // how many letters the window is still missing  let left = 0, bestStart = 0, bestLen = Infinity;  for (let right = 0; right < s.length; right++) {    const c = s[right];    if (need.has(c)) {      if (need.get(c) > 0) missing--;            // we still needed this letter      need.set(c, need.get(c) - 1);              // can go below 0: that means an extra copy    }    while (missing === 0) {                      // the window has all of t: try to make it smaller      if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }      const l = s[left];      if (need.has(l)) {        need.set(l, need.get(l) + 1);        if (need.get(l) > 0) missing++;          // we just lost a letter we needed      }      left++;    }  }  return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);}console.log(minWindow("ADOBECODEBANC", "ABC")); // BANCconsole.log(minWindow("a", "a"));               // aconsole.log(minWindow("a", "aa") === "");       // true

need counts how many copies of each letter we still want. It can go below 0 when the window holds extra copies. missing is one number that tells you at once (O(1)) whether the window is valid. So you never compare whole maps. The time is O(n + m), where m is the length of t. The space is O(m) for the letters of t.

Dry run · minWindow("ADOBECODEBANC", "ABC")

Event	Window	Valid?	Best so far
right reaches C (index 5)	ADOBEC	yes	ADOBEC (6)
shrink: drop A	DOBEC	no	ADOBEC (6)
right reaches A (index 10)	DOBECODEBA	yes (after drops: CODEBA)	ADOBEC (6), because CODEBA is not shorter
right reaches C (index 12)	ODEBANC	yes (after drops: BANC)	BANC (4)

The shortest window is “BANC”.

Practice questions

For each question, first name the three decisions: what the window remembers, when it is not valid, and what to save.

Q1Longest substring without repeating charactersMedium

Return the length of the longest substring of s that has no repeated letter.

Example 1

Input: "abcabcbb"

Output: 3

Explanation: The longest substring with all different letters is "abc".

Example 2

Input: "bbbbb"

Output: 1

Explanation: Only "b".

Example 3

Input: "pwwkew"

Output: 3

Explanation: Either "wke" or "kew". "pwke" is not contiguous (it has gaps).

Stuck? Open one hint at a time

Hint 1

Brute force: try every start position and keep going until a letter repeats. That takes O(n²) time or more.

Hint 2

Keep a window with no repeats. When the new letter is already inside, what must change?

Hint 3

Instead of shrinking one step at a time, could you move left straight past the earlier copy?

Show all 2 solutions with explanations

Approach 1Window with a Set

The idea

Move right forward one letter at a time.
While s[right] is already in the Set, remove s[left] and move left forward.
Add s[right] and save the window length.

JavaScript

function lengthOfLongestSubstring(s) {  const seen = new Set();  let left = 0, best = 0;  for (let right = 0; right < s.length; right++) {    while (seen.has(s[right])) { seen.delete(s[left]); left++; }    seen.add(s[right]);    best = Math.max(best, right - left + 1);  }  return best;}console.log(lengthOfLongestSubstring("abcabcbb")); // 3console.log(lengthOfLongestSubstring("bbbbb"));    // 1console.log(lengthOfLongestSubstring("pwwkew"));   // 3console.log(lengthOfLongestSubstring(""));         // 0

How it works

O(n) time, because each index enters the window once and leaves once. O(alphabet) space, which means the Set never holds more than the number of different letters in the alphabet.

Approach 2Jump with a Map of last positions

The idea

Store the last index (position) of each letter. When a repeat appears inside the window, move left to the spot just after that old copy in one step.

JavaScript

function lengthOfLongestSubstring(s) {  const last = new Map();                    // letter -> last index where we saw it  let left = 0, best = 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 the earlier copy    last.set(c, right);    best = Math.max(best, right - left + 1);  }  return best;}console.log(lengthOfLongestSubstring("abba"));     // 2console.log(lengthOfLongestSubstring("tmmzuxt"));  // 5

How it works

The check last.get(c) >= left is important. An old copy that is already outside the window must be ignored (try “abba”). It is still O(n), with fewer steps.

Which approach should you use?

Both are fine. The Set version is easier to get right when you are nervous in an interview. (LeetCode 3.)

Q2Longest repeating character replacementMedium

You get an uppercase string and a number k. You may replace at most k letters. Return the length of the longest substring made of one repeated letter that you can get.

Example 1

Input: s = "ABAB", k = 2

Output: 4

Explanation: Change both "A"s to "B" (or the reverse): "BBBB".

Example 2

Input: s = "AABABBA", k = 1

Output: 4

Explanation: Change one "B": "AABA" → "AAAA".

Stuck? Open one hint at a time

Hint 1

For one window, how many letters must you change to make all the letters the same?

Hint 2

Answer: the window size minus the count of its most common letter. This number must be at most k.

Show the solution with explanations

Approach 1Window with letter counts

The idea

Keep the count of each letter in the window, and the highest count you have seen (maxFreq).
If size − maxFreq > k, the window needs too many changes, so shrink it from the left.
Save the window size.

JavaScript

function characterReplacement(s, k) {  const count = {};  let left = 0, maxFreq = 0, best = 0;  for (let right = 0; right < s.length; right++) {    count[s[right]] = (count[s[right]] || 0) + 1;    maxFreq = Math.max(maxFreq, count[s[right]]);    while (right - left + 1 - maxFreq > k) {      count[s[left]]--;      left++;    }    best = Math.max(best, right - left + 1);  }  return best;}console.log(characterReplacement("ABAB", 2));    // 4console.log(characterReplacement("AABABBA", 1)); // 4console.log(characterReplacement("AAAA", 0));    // 4

How it works

O(n) time, O(26) space. maxFreq is allowed to be out of date after shrinking, as the lesson explained.

Which approach should you use?

(LeetCode 424.)

Q3Permutation in stringMedium

Return true if s2 contains a permutation of s1 as a substring. Both strings use only lowercase letters.

Example 1

Input: s1 = "ab", s2 = "eidbaooo"

Output: true

Explanation: "ba" is a permutation of "ab".

Example 2

Input: s1 = "ab", s2 = "eidboaoo"

Output: false

Explanation: No window of length 2 has the letters a and b.

Stuck? Open one hint at a time

Hint 1

A permutation of s1 (the same letters in any order) has the same letter counts and the same length.

Hint 2

Slide a window of length s1.length over s2. Update the counts as letters enter and leave.

Show all 2 solutions with explanations

Approach 1Sort each window

The idea

Sort s1. Then for each window of s2, sort the window and compare.

JavaScript

function checkInclusion(s1, s2) {  const target = [...s1].sort().join("");  for (let i = 0; i + s1.length <= s2.length; i++) {    if ([...s2.slice(i, i + s1.length)].sort().join("") === target) return true;  }  return false;}console.log(checkInclusion("ab", "eidbaooo")); // trueconsole.log(checkInclusion("ab", "eidboaoo")); // false

How it works

About O(n · m log m) time, where n is the length of s2 and m is the length of s1 (there are about n windows and sorting one costs m log m). This is too slow when both strings are long.

Approach 2Fixed-size window with counts

The idea

Keep two arrays of 26 counts. Add the letter that enters, remove the letter that leaves, and compare the arrays.

JavaScript

function checkInclusion(s1, s2) {  if (s1.length > s2.length) return false;  const idx = (c) => c.charCodeAt(0) - 97;  const need = new Array(26).fill(0), win = new Array(26).fill(0);  for (const c of s1) need[idx(c)]++;  for (let i = 0; i < s2.length; i++) {    win[idx(s2[i])]++;    if (i >= s1.length) win[idx(s2[i - s1.length])]--;    if (i >= s1.length - 1 && need.every((n, j) => n === win[j])) return true;  }  return false;}console.log(checkInclusion("ab", "eidbaooo")); // trueconsole.log(checkInclusion("ab", "eidboaoo")); // falseconsole.log(checkInclusion("abc", "ab"));      // false

How it works

O(26 · n) = O(n) time, O(26) space.

Which approach should you use?

Use the fixed-size window version. (LeetCode 567.)

Q4Find all anagrams in a stringMedium

Return the start index of every substring of s that is an anagram of p.

Example 1

Input: s = "cbaebabacd", p = "abc"

Output: [0, 6]

Explanation: "cba" starts at 0 and "bac" at 6.

Example 2

Input: s = "abab", p = "ab"

Output: [0, 1, 2]

Explanation: "ab", "ba", "ab".

Stuck? Open one hint at a time

Hint 1

This is question 3. The only change is that you collect every start index instead of stopping at the first one.

Show all 2 solutions with explanations

Approach 1Fixed-size window with counts

The idea

Slide a window of length p.length and compare its counts with the counts of p. Every time they match, add the start index to the result.

JavaScript

function findAnagrams(s, p) {  const idx = (c) => c.charCodeAt(0) - 97;  const need = new Array(26).fill(0), win = new Array(26).fill(0);  for (const c of p) need[idx(c)]++;  const out = [];  for (let i = 0; i < s.length; i++) {    win[idx(s[i])]++;    if (i >= p.length) win[idx(s[i - p.length])]--;    if (i >= p.length - 1 && need.every((n, j) => n === win[j])) out.push(i - p.length + 1);  }  return out;}console.log(findAnagrams("cbaebabacd", "abc")); // [0, 6]console.log(findAnagrams("abab", "ab"));        // [0, 1, 2]console.log(findAnagrams("a", "ab"));           // []

How it works

O(n) time, O(1) space.

Approach 2Window with a single mismatch counter

The idea

Do not compare 26 counts at every step. Just track how many letters are still missing, like in minimum window.

JavaScript

function findAnagrams(s, p) {  const need = new Map();  for (const c of p) need.set(c, (need.get(c) || 0) + 1);  let missing = p.length;  const out = [];  for (let i = 0; i < s.length; i++) {    const add = s[i];    if (need.has(add)) { if (need.get(add) > 0) missing--; need.set(add, need.get(add) - 1); }    if (i >= p.length) {      const drop = s[i - p.length];      if (need.has(drop)) { need.set(drop, need.get(drop) + 1); if (need.get(drop) > 0) missing++; }    }    if (missing === 0) out.push(i - p.length + 1);  }  return out;}console.log(findAnagrams("cbaebabacd", "abc")); // [0, 6]console.log(findAnagrams("abab", "ab"));        // [0, 1, 2]

How it works

It is still O(n), but each step costs O(1) because there is no 26-number comparison. It also works for any characters, not only lowercase letters.

Which approach should you use?

Use the first for clarity. The second is the more general technique. (LeetCode 438.)

Q5Minimum window substringHard

Return the smallest substring of s that contains every letter of t (as many times as it appears in t). If there is none, return "".

Example 1

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

Explanation: The shortest substring that has A, B and C.

Example 2

Input: s = "a", t = "a"

Output: "a"

Explanation: The whole string.

Example 3

Input: s = "a", t = "aa"

Output: ""

Explanation: There are not enough a's.

Stuck? Open one hint at a time

Hint 1

Move the right edge forward until the window has every letter of t (with the right counts).

Hint 2

Then shrink from the left for as long as the window stays valid. Save the smallest window you see.

Hint 3

Keep a missing number, so that the question “is the window valid?” takes O(1).

Show all 2 solutions with explanations

Approach 1Check every substring

The idea

For every start and end, count the letters in that piece and test it.

JavaScript

function minWindow(s, t) {  const covers = (sub) => {    const c = {};    for (const ch of sub) c[ch] = (c[ch] || 0) + 1;    for (const ch of t) { if (!c[ch]) return false; c[ch]--; }    return true;  };  let best = "";  for (let i = 0; i < s.length; i++) {    for (let j = i + t.length; j <= s.length; j++) {      const sub = s.slice(i, j);      if ((best === "" || sub.length < best.length) && covers(sub)) best = sub;    }  }  return best;}console.log(minWindow("ADOBECODEBANC", "ABC")); // BANC

How it works

O(n³) time or worse. Use it only as a starting point.

Approach 2Grow, then shrink (the template)

The idea

Count the letters you need from t. Set missing = t.length.
Move right forward. Each needed letter lowers missing.
While missing === 0, save the window and move left forward, which gives letters back.

JavaScript

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, bestStart = 0, bestLen = Infinity;  for (let right = 0; right < s.length; right++) {    const c = s[right];    if (need.has(c)) { if (need.get(c) > 0) missing--; need.set(c, need.get(c) - 1); }    while (missing === 0) {      if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }      const l = s[left];      if (need.has(l)) { need.set(l, need.get(l) + 1); if (need.get(l) > 0) missing++; }      left++;    }  }  return bestLen === Infinity ? "" : s.slice(bestStart, bestStart + bestLen);}console.log(minWindow("ADOBECODEBANC", "ABC")); // BANCconsole.log(minWindow("a", "a"));               // aconsole.log(minWindow("a", "aa") === "");       // trueconsole.log(minWindow("aa", "aa"));             // aa

How it works

O(n + m) time, because each pointer moves forward at most n times. O(m) space for the needed letters.

Which approach should you use?

Use the template. This question is marked “Hard”, but it is just the window template done carefully. (LeetCode 76.)

Q6Longest substring with at most K distinct charactersMedium

Return the length of the longest substring that has at most k different letters.

Example 1

Input: s = "eceba", k = 2

Output: 3

Explanation: "ece" has two distinct letters.

Example 2

Input: s = "aa", k = 1

Output: 2

Explanation: The whole string.

Stuck? Open one hint at a time

Hint 1

What does the window remember? How many times each letter appears, and so how many different letters there are.

Hint 2

The window is not valid when the Map has more than k keys.

Show the solution with explanations

Approach 1Window with a count Map

The idea

Add the letter that enters. While the Map has more than k letters, remove letters from the left. Delete a key when its count reaches 0.

JavaScript

function lengthOfLongestSubstringKDistinct(s, k) {  const count = new Map();  let left = 0, best = 0;  for (let right = 0; right < s.length; right++) {    count.set(s[right], (count.get(s[right]) || 0) + 1);    while (count.size > k) {      const l = s[left];      count.set(l, count.get(l) - 1);      if (count.get(l) === 0) count.delete(l);      left++;    }    best = Math.max(best, right - left + 1);  }  return best;}console.log(lengthOfLongestSubstringKDistinct("eceba", 2)); // 3console.log(lengthOfLongestSubstringKDistinct("aa", 1));    // 2console.log(lengthOfLongestSubstringKDistinct("abc", 0));   // 0

How it works

O(n) time, O(k) space. Deleting a key when its count is 0 is what makes count.size equal the number of different letters.

Which approach should you use?

(LeetCode 340, a paid-only problem. This pattern is the one you will reuse most often.)

Q7Fruit into basketsMedium

Each tree gives one type of fruit. You have two baskets, and each basket holds only one type. You must pick from trees that are next to each other. Return the most fruit you can collect.

Example 1

Input: fruits = [1, 2, 1]

Output: 3

Explanation: Two types, three trees.

Example 2

Input: fruits = [0, 1, 2, 2]

Output: 3

Explanation: Pick [1, 2, 2].

Example 3

Input: fruits = [1, 2, 3, 2, 2]

Output: 4

Explanation: Pick [2, 3, 2, 2].

Stuck? Open one hint at a time

Hint 1

Two baskets, and each basket holds one type. So you want the longest subarray with at most 2 different values.

Hint 2

This is the previous question with k = 2, but on an array.

Show the solution with explanations

Approach 1At most two distinct values

The idea

It is the same window, but on an array instead of a string.

JavaScript

function totalFruit(fruits) {  const count = new Map();  let left = 0, best = 0;  for (let right = 0; right < fruits.length; right++) {    count.set(fruits[right], (count.get(fruits[right]) || 0) + 1);    while (count.size > 2) {      const l = fruits[left];      count.set(l, count.get(l) - 1);      if (count.get(l) === 0) count.delete(l);      left++;    }    best = Math.max(best, right - left + 1);  }  return best;}console.log(totalFruit([1, 2, 1]));       // 3console.log(totalFruit([0, 1, 2, 2]));    // 3console.log(totalFruit([1, 2, 3, 2, 2])); // 4

How it works

O(n) time, O(1) space, because the Map has at most 3 keys. The hard part is to see that this is the same problem in a different story.

Which approach should you use?

(LeetCode 904.)

Dry run · Which window type for which wording?

The question says…	Window	Memory	Not valid when…
longest substring with no repeats	variable	Set of letters	new letter already inside
longest … with at most k changes	variable	letter counts + maxFreq	size − maxFreq > k
longest … with at most k distinct	variable	Map of counts	map.size > k
is there an anagram / permutation	fixed (length p)	26 counts	never; compare at each step
shortest substring containing t	variable	need counts + missing	valid when missing = 0, so shrink

Make it stick

Make it stick — close this page, then

Write the variable-window template and the three decisions every window problem needs.
Explain why you save the longest-window answer after shrinking, and the shortest-window answer inside the loop.
Work out the condition windowSize − maxFreq > k for character replacement.
Explain how the “missing” counter lets you check the minimum window in O(1).

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

Part 7 complete: what's next

You can now solve questions on palindromes, prefixes, compression, and every common window question on text. Part 8 moves from scanning to exploring. You will learn recursion (a function that calls itself) and recursion trees (a drawing of all the calls). Then you will list every subset, permutation and combination with backtracking (try a choice, and undo it if it does not work).

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated 7 Oct 2026 · How these lessons are made

Keep learning

Related series

On this page

A window is two markers and a little memory

The variable-window template

Longest substring without repeating characters

Traced: windows over “abcabcbb”

Longest repeating character replacement

Fixed-size windows: permutations and anagrams

Minimum window substring

Practice questions

Make it stick

Part 7 complete: what's next

Practise on LeetCode

Keep learning