Sliding window

Episode 21 Permutation in String

5 min · LeetCode 567 · Java

Title card of Episode 21: Permutation in String

▶ This video is coming to YouTube soon.

LeetCode 567, Permutation in String, solved on screen. Two examples show what counts: the same letters as s1, side by side, in any order. Then the brute force counts every window of s2 from scratch and compares it with s1's counts: O(n · m). Finally, one fixed-size sliding window adds the letter coming in and removes the one going out, so each step costs O(1): O(n) in all.

What you'll learn

  • What Permutation in String asks, through two worked examples
  • Why equal letter counts mean a permutation
  • The brute force: count every window, O(n · m) time, O(1) space
  • The fixed sliding window: one in, one out, O(n) time, O(1) space
  • Why the letter at right − m is the one that leaves

Chapters

  1. 0:00The problem
  2. 0:16Examples
  3. 0:39Brute force, visualized
  4. 1:21Brute force: the code
  5. 1:38Brute force, line by line
  6. 2:19Sliding window: the idea
  7. 2:38Sliding window, visualized
  8. 3:22Sliding window: the code
  9. 3:39Sliding window, line by line
  10. 4:17Comparing the approaches