DSA sheet · Strings · Sliding Window pattern (fixed size + frequency map)

Find All Anagrams in a String

This is the first sliding-window question of the strings section, and the teacher spends two videos on it. In Part 1 she explains what an anagram is, reads the constraints, and writes a brute force: cut out every substring of length len(p), count its letters, and compare the counts with p's counts. She also compares "sort and compare" against "count and compare", and does a careful time-complexity analysis with different sizes. In Part 2 she says why this is a sliding-window problem and solves it in O(n) two ways: first with two frequency maps (easier to understand), then with one map (less space, the one interviewers like).

Why it matters: "find every window of s that is a rearrangement of p" is the parent of a whole family: Permutation in String (problem 13) is the same code returning True/False, and Minimum Window Substring (problem 14) uses the same "count of still-needed characters" idea with a variable window.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Sliding window from scratch + frequency maps + what an anagram is
• Part A · Brute force: count every substring of length k (video 1)
• Part B · Sliding window with two maps (video 2)
• Part C · Sliding window with one map (video 2)
• Part D · Revision page

Part 0 · Before starting

Substring / subarray = a contiguous piece

A substring (for strings) or subarray (for arrays) is a piece whose characters sit next to each other. You pick a start index and an end index and take everything between them. You may not skip a character in the middle.

The brute force over all windows, and why it repeats work

Many questions say "find the best / count all substrings (or subarrays) that satisfy some rule". The simplest answer is two loops: the outer loop picks the start, the inner loop walks the end forward and re-checks the piece. That is about n² pieces, so O(n²) (or worse, if each check is itself a loop).

The waste: two neighbouring pieces share almost everything. "cba" and "bae" share "ba". The brute force throws away what it learned about "ba" and counts it again from zero. Sliding window keeps the shared middle and only updates the two ends.

The window [left..right]

A window is the current substring, described by two indexes: left (its first character) and right (its last character). Its length is right − left + 1. Two moves change it:

• Expand: move right one step forward. One new character enters, so we add it to whatever we are tracking (a sum, a count, a map).
• Shrink: move left one step forward. One old character leaves, so we undo exactly what we did when it entered.

The teacher's short version: right is responsible for expanding, left is responsible for shrinking, and left always undoes what right did. Both pointers only move forward, never back. Each one walks the string at most once, so the whole thing is about 2n steps = O(n).

Fixed-size vs variable-size windows

def fixed_window(arr, k):
    out = []
    left = 0
    for right in range(len(arr)):
        # 1. add arr[right] to the window's data
        if right - left + 1 > k:       # window became k+1 long
            # 2. remove arr[left] from the window's data
            left += 1                  # exactly one step, so `if` not `while`
        if right - left + 1 == k:
            out.append((left, right))  # 3. use the full window
    return out

Longest valid, shortest valid, count of valid (for the variable kind)

• Longest valid: grow right; while the window breaks the rule, shrink left; then the window is valid → best = max(best, right − left + 1).
• Shortest valid: grow right; while the window still satisfies the rule, record its length and shrink left to try to make it shorter.
• Count of valid: after shrinking, every window that ends at right and starts anywhere from left to right is valid, so count += right − left + 1.
• Exactly K: "exactly K" is hard to slide directly, so use exactly(K) = atMost(K) − atMost(K − 1) (used in problems 8 and 12).

Why sliding window needs a "monotonic" rule

Shrinking is only safe if removing a character can only move the window towards valid (and adding can only move it away, or the other way round, but always the same way). With positive numbers and a sum rule this holds: add → bigger, remove → smaller. With negative numbers it breaks (removing a negative makes the sum bigger), and sliding window gives wrong answers. For this problem the window length is fixed, so we never have to decide "should I shrink?" based on the data at all, which is why it is the easiest kind.

(One more tool you'll meet in problem 9, Sliding Window Maximum: a monotonic deque that keeps window elements in decreasing order so the max is always at the front. Not needed here.)

Frequency map (Counter)

A frequency map stores character → how many times it appears. In Python a dict works, and collections.Counter builds one in a single line.

from collections import Counter

freq = {}
for ch in "abca":
    freq[ch] = freq.get(ch, 0) + 1     # {'a': 2, 'b': 1, 'c': 1}

same = Counter("abca")                 # Counter({'a': 2, 'b': 1, 'c': 1})

arr = [0] * 26                         # only lowercase letters
for ch in "abca":
    arr[ord(ch) - ord('a')] += 1       # index 0 = 'a', 1 = 'b', ... 25 = 'z'

freq.get(ch, 0) means "the count of ch, or 0 if ch isn't in the map yet" (Java's getOrDefault). The 26-slot list works because the question says only lowercase English letters appear: ord(ch) − ord('a') turns 'a' into 0, 'b' into 1, … 'z' into 25.

What is an anagram?

An anagram of a word is any rearrangement (permutation) of its letters, using every letter exactly as many times as in the original. For "abc" the anagrams are: abc, acb, bac, bca, cab, cba (3! = 6 of them). Two strings are anagrams of each other exactly when they have the same length and the same frequency map. The order of letters doesn't matter, only the counts.

Part A · Brute force: count every substring of length k

LeetCode 438 · from video 1

1The question in simple words

You get two strings, s (long) and p (short). Find every place in s where a substring is an anagram of p, and return the list of starting indexes of those substrings.

"cba" starts at index 0 and is a rearrangement of "abc". "bac" starts at index 6 and is too. No other length-3 piece uses exactly one a, one b and one c. So the answer is [0, 6]. The question wants the start index of each anagram, not the substrings themselves.

2What the constraints tell us

• 1 ≤ len(s), len(p) ≤ 3·10⁴. The teacher's rule of thumb: up to about 10⁸ simple operations is safe; 2–5·10⁸ sometimes passes if the logic is very light; beyond that (7·10⁸, 8·10⁸, 9·10⁸…) you get TLE. An O(n²) solution here could reach (3·10⁴)² = 9·10⁸, so even simple O(n²) code is in danger. We will need to optimise, but she writes the brute force first.
• Only lowercase English letters. So there are only 26 possible characters, and a fixed 26-slot count array is enough. Its size never grows with n, so it counts as O(1) space.
• p can be longer than s. Then no substring of s can have p's length, and the answer is an empty list.

3Intuition: cut out every piece of length k and check it

Let k = len(p). An anagram of p must have length k, so we only care about substrings of length exactly k. Line them up: "cba", "bae", "aeb", "eba", "bab", "aba", "bac", "acd". For each one, ask "is this a rearrangement of p?" If yes, remember where it started.

4Building the logic from examples

How do we check "is this piece an anagram of p"? Two ways

1. Sort both and compare: sorted("cba") = "abc" = sorted("abc") ✓. No extra array needed, but every check costs a sort.
2. Count both and compare: make a 26-slot count array for p (p_count) and one for the piece (s_count). For p = "abc": a → 1, b → 1, c → 1, all other slots 0. For the piece "cba": c → 1, b → 1, a → 1. The two arrays are equal → anagram ✓.

Where can a piece start?

Call the start index i. The piece is s[i], s[i+1], …, s[i+k−1]. The last legal start is the one where the piece ends exactly at the last index n−1, so i + k − 1 = n − 1, which means i = n − k. So i runs from 0 to n − k, both included, which is n − k + 1 pieces. For s = "cbaebabacd" (n = 10), k = 3: i goes 0…7, 8 pieces. If you start at index 8, only two letters ("cd") are left, so it can't hold a 3-letter anagram.

5Approach steps

1. Make result = [], and let n = len(s), k = len(p).
2. Build p_count: 26 zeros, then +1 for every letter of p.
3. For every start i from 0 to n − k: make a fresh s_count of 26 zeros and count s[i … i+k−1] into it.
4. If s_count == p_count, append i to result.
5. Return result.

6Code (Python)

class Solution:
    def findAnagrams(self, s, p):
        result = []
        n, k = len(s), len(p)

        p_count = [0] * 26
        for ch in p:
            p_count[ord(ch) - ord('a')] += 1

        for i in range(n - k + 1):              # every legal start (empty if k > n)
            s_count = [0] * 26                  # fresh counts for this piece
            for j in range(i, i + k):           # s[i .. i+k-1]
                s_count[ord(s[j]) - ord('a')] += 1
            if s_count == p_count:              # same letters, same counts
                result.append(i)                # store the START index
        return result

class Solution:
    def findAnagrams(self, s, p):
        k = len(p)
        target = sorted(p)
        return [i for i in range(len(s) - k + 1)
                if sorted(s[i:i + k]) == target]

7Code line by line

8Dry run (hand table)

s = "cbaebabacd", p = "abc", so p_count has a:1, b:1, c:1. Only non-zero slots are shown.

Final answer: [0, 6] ✓. Notice how rows 1, 2, 3 count "a", "b", "e" over and over. That repetition is what Part B removes.

9Complexity & remember

The teacher works out the time by trying different sizes, to show that "plug in the biggest k" is not automatically the worst case.

• Building p_count costs k steps. The outer loop runs n − k + 1 times; each time the inner loop runs k times (plus 26 for the compare). Total ≈ (n − k + 1) · k.
• k almost equal to n (say both 10⁴): the outer loop runs only a handful of times, the inner one about n → roughly 2n steps. That's a good case, even though k is huge.
• n = 10⁴, k = 10³: outer ≈ 9,000, inner = 1,000 → 9·10⁶ steps. That's already "near n²" behaviour.
• My addition: the product (n − k)·k is biggest when k ≈ n/2, giving about n²/4. With n = 3·10⁴ that's ≈ 2.25·10⁸, right at the danger line. So call it O(n·k), which is O(n²) in the worst case.
• Space O(1): two arrays of 26, fixed size.
• Sorting version: (n − k + 1) · k log k time. Slower by the log factor.

She submitted the counting version: accepted, but slow. So she looks for a better pattern.

Part B · Sliding window with two maps

LeetCode 438 · from video 2

1The question again, with the new goal

Same question (all start indexes of anagrams of p in s), same example: s = "cbaebabacd", p = "abc" → [0, 6]. The goal now is one pass over s, O(n), with no inner loop.

2What the constraints tell us now

• n up to 3·10⁴ → we want O(n). O(n) is only 3·10⁴ steps.
• Lowercase letters only → each map holds at most 26 keys, so the maps are O(1) space in the strict sense (the teacher still calls this "two maps" vs "one map" when comparing space).
• If len(s) < len(p) → return [] straight away (her base case).

3Intuition: why sliding window, and the "count" idea

Why sliding window? The teacher gives two reasons:

1. Strings have two main patterns. Two pointers is for comparing or computing with exactly two positions (a left character and a right character). Sliding window is for questions about a substring/subarray (everything between left and right). We want substrings → sliding window.
2. The brute force repeats work: when we moved from "cba" to "bae" we re-counted "ba". Sliding window keeps the middle and only changes the ends, turning two loops into one.

The picture: keep a window of length k sliding over s. Keep two maps:

• p_map: what we need, letter → count in p. Built once, never changes.
• s_map: what the window has, letter → count inside the window.

Comparing two maps every step would be slow-ish, so she adds one number: count = how many required characters the window is still missing. It starts at len(p) (we're missing all 3). Every time a useful character enters, count goes down by 1. When count == 0 and the window has length k, the window holds exactly the letters of p → anagram.

4Building the logic from examples

Example 1: "cba…" – expanding and reducing count

count = 3. right reads c: is c in p_map with a count > 0? Yes → it's needed. Put it in s_map (c:1) and count → 2. right reads b: needed → s_map b:1, count → 1. right reads a: needed → a:1, count → 0. Count 0 means every required character has been seen in the window, and the window length is 3 = k → valid. Store the start, which is left = 0 (not right!).

Note that every character right reads goes into s_map, needed or not. Only count is touched just for needed ones.

Example 2: "eabc" – why we sometimes have to shrink

Imagine s = "eabc", p = "abc". right reads e (not needed, count stays 3), then a (2), b (1), c (0). count is 0, but the window is "eabc", length 4. The answer is the start of "abc" (index 1), not the start of "eabc". So count 0 is not enough on its own; the length must also be exactly k. When the window is longer than k, we shrink from the left. In "cba" the length was already 3, so no shrinking was needed there.

Shrinking: left undoes what right did

Back to "cbaebabacd". After storing 0, right reads e → window "cbae", length 4 > 3 → shrink. The letter leaving is c. Before it leaves, the window had everything; after it leaves, "bae" is missing a c. So count must go back up to 1 ("I need one more character").

In code: if the left character is in p_map and it was a required copy (s_map[ch] ≤ p_map[ch]), then count += 1. In both cases, s_map[ch] −= 1 (undo right's +1), and left += 1.

The tricky part: duplicates. "Present in p" is not enough

Now window is "bae" (count 1, missing c). right reads b → s_map b becomes 2. If our rule were only "b is in p_map", we would lower count to 0 and wrongly call "aeb"(+b) valid. But p needs only one b, and the window already had one. The second b is extra.

So the rule when a character enters is: after adding it, if s_map[ch] ≤ p_map[ch], it was needed → count −= 1; if s_map[ch] > p_map[ch], it's extra → leave count alone. The teacher acts it out: s_map says "I've seen two b's", p_map says "I only need one. If you're equal to me or below, I'll take it. You're above me, so this b is not useful."

The same rule protects shrinking: if the leaving b has s_map[b] = 2 while p_map[b] = 1, there is still another b inside, so losing this one doesn't hurt → count unchanged. Only when s_map[ch] ≤ p_map[ch] (we're about to drop below what's needed) does count go up.

5Approach steps

1. If len(s) < len(p): return [].
2. Build p_map from p. s_map = {}, left = 0, count = len(p).
3. For right from 0 to n−1: ch = s[right]; s_map[ch] += 1.
4. If ch is in p_map and s_map[ch] ≤ p_map[ch] → count −= 1 (a needed character came in).
5. If the window length right−left+1 > k: let lc = s[left]. If lc is in p_map and s_map[lc] ≤ p_map[lc] → count += 1. Then s_map[lc] −= 1, left += 1.
6. If count == 0 → append left.
7. Return the result.

6Code (Python)

from collections import Counter

class Solution:
    def findAnagrams(self, s, p):
        result = []
        if len(s) < len(p):                     # base case: no room for an anagram
            return result

        p_map = Counter(p)                      # what we NEED
        s_map = {}                              # what the window HAS
        left = 0
        count = len(p)                          # needed characters still missing
        k = len(p)

        for right in range(len(s)):
            ch = s[right]
            s_map[ch] = s_map.get(ch, 0) + 1    # every char enters the map
            if ch in p_map and s_map[ch] <= p_map[ch]:
                count -= 1                      # a needed copy arrived

            if right - left + 1 > k:            # window too long: shrink once
                lc = s[left]
                if lc in p_map and s_map[lc] <= p_map[lc]:
                    count += 1                  # losing a needed copy
                s_map[lc] -= 1                  # undo what right did
                left += 1

            if count == 0:                      # length is k and nothing missing
                result.append(left)
        return result

7Code line by line

8Dry run (hand table, s_map after every slide)

s = "cbaebabacd", p = "abc", k = 3, p_map = {a:1, b:1, c:1}. Start: s_map = {}, left = 0, count = 3. "needed" means s_map[ch] ≤ p_map[ch] after the +1.

right goes past the end → loop ends → return [0, 6] ✓.

The string at three key moments (yellow = window, grey = already left behind):

9Complexity & remember

• Time O(n): building p_map is O(k); right moves 0 → n−1 once, left moves forward at most n times; neither pointer ever goes back. About 2n steps, so linear. (In the video she says "O of one" once by slip; she means one pass, O(n).) Her Java submission was fast.
• Space: two maps. With only 26 letters each, that's O(1) in big-O terms, but it's twice the memory of Part C.

Part C · Sliding window with one map

LeetCode 438 · from video 2 · same window, same count, half the maps

1What stays the same

Same question, same constraints, same fixed-size window, same count of missing characters, same "shrink once with if", same "store left when count == 0". Time is the same O(n). Only the bookkeeping changes: we drop s_map and let one map, need, mean "how many more of this letter the window still needs". The teacher's view: one-map is not harder, it just makes more sense after you've seen two maps. Interviewers usually prefer this one because it uses less space.

2Intuition: one map that counts down

• Start with need = p's counts: a:1, b:1, c:1.
• When right brings in a letter, decrease need[letter]. Going down towards 0 means "one fewer still needed". (Increasing would make no sense: we'd never be able to say "all found".)
• A letter that isn't in p at all (like e) gets added to the map starting at 0 and then decreased to −1.
• Negative = "the window has more of this letter than p wants". It's extra, or as she puts it, it was added to the substring for nothing.
• When left lets a letter go, increase need[letter] (left undoes right).

3Building the conditions

When right adds a letter: did it reduce count?

It's needed if need[ch] was positive before we decrease it. Two equal ways to write it:

• Check first, then decrease: if need[ch] > 0: count −= 1, then need[ch] −= 1.
• Decrease first, then check: need[ch] −= 1, then if need[ch] >= 0: count −= 1. After decreasing, a needed letter lands on 0 or more; an extra one lands below 0.

When left removes a letter: did it increase count?

Look at need[lc] before increasing it. If it's ≥ 0, this copy was a needed one: when right brought it in, need was positive and went down to this value. Losing it means we're missing one → count += 1. If it's negative, the window has a spare copy, so count stays. Either way, need[lc] += 1, then left += 1.

Her example: window "cbae" with need = {a:0, b:0, c:0, e:−1}. c leaves: need[c] = 0, which is ≥ 0 → it was needed → count 0 → 1, and need[c] becomes 1 ("we need one c again").

4Approach steps

1. If len(s) < len(p): return [].
2. need = counts of p; left = 0; count = len(p).
3. For each right: ch = s[right]. If need.get(ch, 0) > 0 → count −= 1. Then need[ch] = need.get(ch, 0) − 1.
4. If the window is longer than k: lc = s[left]; if need[lc] ≥ 0 → count += 1; need[lc] += 1; left += 1.
5. If count == 0 → append left.
6. Return result.

5Code (Python)

class Solution:
    def findAnagrams(self, s, p):
        result = []
        if len(s) < len(p):
            return result

        need = {}                               # letter -> how many still needed
        for ch in p:
            need[ch] = need.get(ch, 0) + 1
        left = 0
        count = len(p)
        k = len(p)

        for right in range(len(s)):
            ch = s[right]
            if need.get(ch, 0) > 0:             # check first ...
                count -= 1                      # ... it was needed
            need[ch] = need.get(ch, 0) - 1      # then decrease (may go negative)

            if right - left + 1 > k:
                lc = s[left]
                if need[lc] >= 0:               # it was a needed copy
                    count += 1
                need[lc] += 1                   # undo what right did
                left += 1

            if count == 0:
                result.append(left)
        return result

class Solution:
    def findAnagrams(self, s, p):
        result = []
        if len(s) < len(p):
            return result
        need = {}
        for ch in p:
            need[ch] = need.get(ch, 0) + 1
        left, count, k = 0, len(p), len(p)
        for right in range(len(s)):
            ch = s[right]
            need[ch] = need.get(ch, 0) - 1      # decrease first ...
            if need[ch] >= 0:                   # ... so the test is >= 0
                count -= 1
            if right - left + 1 > k:
                lc = s[left]
                if need[lc] >= 0:
                    count += 1
                need[lc] += 1
                left += 1
            if count == 0:
                result.append(left)
        return result

6Code line by line (only the lines that differ from Part B)

7Dry run (hand table, the one map after every slide)

s = "cbaebabacd", p = "abc". Start: need = {a:1, b:1, c:1}, left = 0, count = 3. "need before" is the value right sees before it decreases.

return [0, 6] ✓. Notice: at every valid window (steps 3 and 9) all of p's letters show exactly 0, and nothing is negative.

8The "eabc" example with one map

s = "eabc", p = "abc": e → need e:−1 (count 3); a → a:0 (2); b → b:0 (1); c → c:0 (0), but length 4 → shrink: e leaves with need −1 (spare) → count stays 0, e back to 0, left = 1 → count 0 → store 1. Answer [1] ✓, the start of "abc", not of "eabc".

9Complexity & remember

• Time O(n), same as two maps: each pointer moves forward at most n times.
• Space: one map instead of two (at most 26 + a few keys). Less space doesn't change the speed, but it's the version interviewers usually expect.

Part D · Revision page

sol = Solution()
print(sol.findAnagrams("cbaebabacd", "abc"))   # [0, 6]
print(sol.findAnagrams("abab", "ab"))          # [0, 1, 2]
print(sol.findAnagrams("eabc", "abc"))         # [1]
print(sol.findAnagrams("xab", "ab"))           # [1]
print(sol.findAnagrams("a", "ab"))             # []
print(sol.findAnagrams("aaaa", "aa"))          # [0, 1, 2]

Based on these videos: Find All Anagrams in a String · Part 1 (brute force) · Find All Anagrams in a String · Part 2 (sliding window: two maps & one map)