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

Permutation in String

Here the teacher solves the same question three times, each one better than the last. First a brute force with two loops and a map per substring. Then a sliding window with two frequency arrays (the fastest on LeetCode). Then a space-optimised sliding window with one map and a count, the version an interviewer may push you towards. Along the way she explains why an array beats a hashmap when the alphabet is fixed, and why a key whose count drops to 0 has to be deleted from a map.

Why it matters: "does s2 contain some rearrangement of s1 as a contiguous piece?" is the yes/no twin of Find All Anagrams (problem 10). Learn one and you know both. The "count of characters still needed" trick from Part C comes back in Minimum Window Substring.

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 arrays/maps + what a permutation is
• Part A · Brute force: every substring, one map each
• Part B · Sliding window with two frequency arrays
• Part C · Space-optimised: one map + count
• Part D · Revision page

Part 0 · Before starting

Substring = contiguous

A substring is a run of characters that sit side by side in the string (for arrays the same idea is called a subarray). You choose where it starts and where it ends and take everything in between. You can't jump over a character.

Brute force over all windows repeats work

The plain way to handle "some substring must satisfy a rule" is two loops: pick a start, then walk an end forward and test each piece. That's about n² pieces → O(n²). The waste is that neighbouring pieces overlap. The teacher's example: s1 = "abcdf", s2 = "abcdifgh…". The piece "abcdi" fails. The next piece "bcdif" checks b, c, d again, even though we just counted them. Sliding window keeps the overlap and only updates the edges.

The window [left..right]: expand and shrink

The current piece is called the window. left is its first index, right its last, and its length is right − left + 1.

• Expand (right += 1): a new character comes in → add it to our counts.
• Shrink (left += 1): the oldest character goes out → undo exactly what we did when it came in.

As the teacher keeps saying, expansion belongs to right, shrinking belongs to left, and left undoes whatever right did. Neither pointer ever goes backwards, so together they make at most 2n moves: O(n). That's how two loops become one.

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 counts
        if right - left + 1 > k:       # one too many
            # 2. remove arr[left] from the counts
            left += 1
        if right - left + 1 == k:
            out.append((left, right))  # 3. test the full window
    return out

The variable-window family, in one breath

• Longest valid: expand; while invalid, shrink; then best = max(best, right − left + 1).
• Shortest valid: expand; while still valid, record the length and shrink.
• Count of valid: after shrinking, all windows ending at right and starting between left and right are valid → count += right − left + 1.
• Exactly K: exactly(K) = atMost(K) − atMost(K − 1).
• All of these need a monotonic rule: adding can only push the window one way, removing only the other way. Sums of positive numbers obey this; with negative numbers it breaks and sliding window gives wrong answers. (Problem 9 adds a monotonic deque to track the window maximum.)

This problem is the simplest kind: the window length is fixed at len(s1), so the shrink decision never depends on the data.

Frequency array vs frequency map

A frequency map stores character → how many times it appears. In Python, a dict or collections.Counter. When the characters can only be the 26 lowercase letters, a frequency array of 26 slots does the same job: slot ord(ch) − ord('a') holds the count of ch.

from collections import Counter

arr = [0] * 26
for ch in "abca":
    arr[ord(ch) - ord('a')] += 1      # arr[0]=2 (a), arr[1]=1 (b), arr[2]=1 (c)

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

same = Counter("abca")                # the same counts in one line

What is a permutation?

A permutation of a string is any rearrangement of all its characters, each used as many times as in the original. For "ab" there are two: "ab" and "ba". Two strings are permutations of each other exactly when they have the same length and the same count of every character. That's the whole test we'll use, so order never needs to be checked.

Part A · Brute force: every substring, one map each

LeetCode 567

1The question in simple words

You get two strings, s1 (short) and s2 (long). Return True if some contiguous piece of s2 is a permutation of s1, otherwise False.

In the second string both b and a are there, but an o sits between them. Permutations of "ab" are "ab" and "ba"; neither appears side by side, so the answer is False.

2What the constraints tell us

• 1 ≤ len(s1), len(s2) ≤ 10⁴. n² = 10⁸. Her rule: with simple logic, up to about 10⁸ (even 2–4·10⁸) is OK; beyond that, TLE. So O(n²) survives but is slow. Still worth optimising.
• Only lowercase English letters. She points this out on purpose: it means a 26-slot array is enough (used in Part B).
• Base case: if len(s1) > len(s2), no piece of s2 is long enough → return False immediately. (If s1 = "abc" and s2 = "ab", why even search?)

3Intuition

A permutation of s1 has exactly len(s1) characters, so look at every piece of s2 of that length. For each, count its letters into a map and compare with s1's map. Equal maps → True. Example: s1 = "ab" → {a:1, b:1}. Pieces of s2 = "eidbaooo": "ei", "id", "db", "ba" → {b:1, a:1} equals {a:1, b:1} → True.

4Building the logic

She uses two loops: i = start of the piece, j = end of the piece, moving forward from i. Each step adds s2[j] to a map that belongs to this start i (a fresh map per i).

• i = 0, j = 0: piece "e", map {e:1}. Too short to compare with "ab".
• j = 1: piece "ei", map {e:1, i:1}. Now the piece has the right length → call match → not equal.
• j = 2: piece "eid". It's already longer than s1, and it'll only get longer. Nothing starting at i = 0 can work → break and move to i = 1.
• i = 1 ("id") and i = 2 ("db") fail the same way. i = 3 starts at "b": map {b:1}, then "ba" → {b:1, a:1} → match → return True.

If every start fails, return False after the loops. A mismatch is never a reason to return False early: a later piece may still match.

5Approach steps

1. If len(s1) > len(s2): return False.
2. Build need = counts of s1.
3. For each start i: make an empty map window.
4. For j from i: add s2[j] to window. When the length j − i + 1 reaches n: if window equals need → return True; otherwise break.
5. After all starts: return False.

6Code (Python)

class Solution:
    def checkInclusion(self, s1, s2):
        n, m = len(s1), len(s2)
        if n > m:
            return False

        need = {}
        for ch in s1:
            need[ch] = need.get(ch, 0) + 1

        for i in range(m):                      # start of the piece
            window = {}                         # fresh map for this start
            for j in range(i, m):               # end of the piece
                window[s2[j]] = window.get(s2[j], 0) + 1
                if j - i + 1 == n:              # length check, NOT map size
                    if self.match(window, need):
                        return True
                    break                       # longer pieces are useless
        return False

    def match(self, a, b):
        return a == b                           # same keys, same counts

7Code line by line

8Dry run (hand table)

s1 = "ab" (need = {a:1, b:1}), s2 = "eidbaooo".

For s2 = "eidboaoo" the length-2 pieces are ei, id, db, bo, oa, ao, oo; none equals {a:1, b:1} → False ✓. Again, rows i = 1, 2, … each re-count a letter the previous row had already counted.

9Complexity & remember

• Time: the outer loop runs m times, the inner loop up to n times before it breaks, plus a map comparison. She calls it O(n²); more exactly O(m·n). With 10⁴ that's about 10⁸: no TLE, but slow.
• Space: two maps of at most 26 keys → O(1).

Part B · Sliding window with two frequency arrays

1The question again, with the new goal

Same question. Goal: one pass over s2 instead of two nested loops, by reusing the counts from the previous window.

2What the constraints tell us now

• Lowercase letters only → two arrays of 26 (freq1 for s1, freq2 for the window) instead of hashmaps. Faster, no hashing.
• Comparing two 26-slot arrays is a fixed 26 steps, so doing it at every position is still linear.

3Intuition: why sliding window

Strings have two patterns in this sheet. Two pointers is for comparing exactly two characters (one at each pointer). Here we care about every character in a contiguous piece, so it's sliding window. And the brute force has the repetition we saw in Part 0 (b, c, d counted again for "bcdif"). Sliding window removes it.

Picture: a frame of width len(s1) sliding along s2 one letter at a time. When it slides, one letter enters on the right and one leaves on the left. freq2 changes in just two slots. Then we compare freq2 with freq1.

4Building the logic from the example

s1 = "ab", s2 = "eidbaooo". left = right = 0 at e.

• right reads e: e:1. Window "e", only 1 long. Nothing to compare yet.
• right reads i: e:1, i:1. Window "ei", length 2 = len(s1) → compare with {a:1, b:1} → no.
• right reads d: window "eid" is length 3, too long. The brute force would break here and restart from the next i. Sliding window instead moves left forward by one, in the same loop: e leaves, so left undoes right's work for e → e:0. Window "id" → compare → no.
• right reads b, i leaves → "db" → no. right reads a, d leaves → "ba" → b:1, a:1 → match → True.

5Approach steps

1. If len(s1) > len(s2): return False.
2. freq1 = counts of s1 in 26 slots; freq2 = 26 zeros; left = 0.
3. For right over s2: freq2[s2[right]] += 1.
4. If the window is longer than n: freq2[s2[left]] −= 1; left += 1.
5. If the window is exactly n: compare the 26 slots; if all equal → return True.
6. After the loop: return False.

6Code (Python)

class Solution:
    def checkInclusion(self, s1, s2):
        n = len(s1)
        if n > len(s2):
            return False

        freq1 = [0] * 26                        # what s1 has
        freq2 = [0] * 26                        # what the window has
        for ch in s1:
            freq1[ord(ch) - ord('a')] += 1

        left = 0
        for right in range(len(s2)):
            freq2[ord(s2[right]) - ord('a')] += 1      # expand

            if right - left + 1 > n:                   # shrink: left undoes right
                freq2[ord(s2[left]) - ord('a')] -= 1
                left += 1

            if right - left + 1 == n:                  # full window: compare
                is_match = True
                for i in range(26):
                    if freq1[i] != freq2[i]:
                        is_match = False
                        break                          # only this window fails
                if is_match:
                    return True
        return False

class Solution:
    def checkInclusion(self, s1, s2):
        n = len(s1)
        if n > len(s2):
            return False
        need = {}
        for ch in s1:
            need[ch] = need.get(ch, 0) + 1
        window = {}
        left = 0
        for right in range(len(s2)):
            window[s2[right]] = window.get(s2[right], 0) + 1
            if right - left + 1 > n:
                lc = s2[left]
                window[lc] -= 1
                if window[lc] == 0:
                    del window[lc]                     # keep no stale keys
                left += 1
            if right - left + 1 == n and window == need:
                return True
        return False

7Code line by line

8Dry run (hand table, freq2 after every slide, zeros hidden)

s1 = "ab" → freq1 = {a:1, b:1}. s2 = "eidbaooo".

The False example, s2 = "eidboaoo", all the way through:

Loop ends → return False ✓. At step 5 the window "dbo" has b and step 6 adds a, but by then b has already left: they're never inside the same length-2 window.

9Complexity & remember

• Time O(n + 26·m) = O(n + m): O(n) to fill freq1, one pass over s2 (m steps), and a 26-step compare at each step. 26 is a constant. On LeetCode this was the fastest of the three.
• Space O(26 + 26) = O(1): two small arrays.

Part C · Space-optimised: one map + count

1Why another version?

Part B is already linear and fast. But it keeps two count structures. If the alphabet were big (thousands of different characters instead of 26), two structures plus a full compare at every step would be costly, and an interviewer may ask: can you do it with one map, and without comparing all slots every time? That's this part. It's the same idea as the one-map solution of Find All Anagrams.

2What stays the same

Same question, constraints and base case (len(s1) > len(s2) → False). Same window of length len(s1), same "left undoes right".

3Intuition: one map that counts down, plus a number

• need: starts as s1's counts, {a:1, b:1}. It means "how many more of this letter the window still needs".
• count: how many needed letters are still missing. Starts at len(s1) = 2.
• When right brings a letter whose need is positive, it's one we wanted → count −= 1. Then need −= 1 in every case.
• A letter s1 doesn't have (like e) starts at 0 and goes to −1: negative = "in the window but not wanted".
• count == 0 → all wanted letters are inside a window of length len(s1) → return True. No 26-slot compare needed.

4Building the logic from the example

s1 = "ab", s2 = "eidbaooo". need = {a:1, b:1}, count = 2, left = 0.

1. right = e: need[e] is 0 (missing → default 0), not positive → count stays 2. need[e] → −1. Window "e", length 1: not full yet.
2. right = i: not wanted, need[i] → −1, count 2. Window "ei" has length 2 = len(s1), and count isn't 0, so it's not a permutation. Since it's full and failed, drop the left letter now. e has need −1, which is negative → e was never one we wanted, so count stays. need[e] back to 0, left → 1.
3. right = d: need[d] → −1. Window "id" full, count 2 → drop i (−1, unwanted) → need[i] = 0, left → 2.
4. right = b: need[b] is 1 > 0 → wanted → count 1. need[b] → 0. Window "db" full, count 1 → drop d (−1, unwanted) → need[d] = 0, left → 3.
5. right = a: need[a] is 1 > 0 → count 0. need[a] → 0. count == 0 → return True ("ba").

5Approach steps

1. If len(s1) > len(s2): return False.
2. need = counts of s1; count = len(s1); left = 0.
3. For each right: ch = s2[right]. If need.get(ch, 0) > 0 → count −= 1. Then need[ch] = need.get(ch, 0) − 1.
4. If count == 0 → return True.
5. Else, if the window length equals len(s1): lc = s2[left]; if need[lc] ≥ 0 → count += 1; need[lc] += 1; left += 1.
6. After the loop: return False.

6Code (Python)

class Solution:
    def checkInclusion(self, s1, s2):
        if len(s1) > len(s2):
            return False

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

        for right in range(len(s2)):
            ch = s2[right]
            if need.get(ch, 0) > 0:              # we wanted this one
                count -= 1
            need[ch] = need.get(ch, 0) - 1       # always: it is in the window now

            if count == 0:                       # full window, nothing missing
                return True

            if right - left + 1 == len(s1):      # full but not valid: drop left
                lc = s2[left]
                if need[lc] >= 0:                # it was a wanted copy
                    count += 1
                need[lc] += 1                    # left undoes right
                left += 1
        return False

7Code line by line

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

s1 = "ab", s2 = "eidboaoo" (the False example, so we see every step). Start: need = {a:1, b:1}, count = 2, left = 0. "need before" is the value right sees before decreasing.

"…" = e:0 i:0 d:0, which don't change after step 4.

count never hit 0 → return False ✓. With s2 = "eidbaooo" the first four steps are the same, then step 5 brings in a (need 1 → count 0) → return True on the window "ba".

9Complexity & remember

• Time O(n + m): one loop to fill the map, one pass over s2. No 26-slot compare inside the loop anymore.
• Space: one map instead of two structures (26 instead of 2 × 26 here; it matters more when the alphabet is large).
• Her LeetCode run was slower than Part B anyway, because a hashmap pays for hashing on each access. Less memory isn't always more speed. With a 26-letter alphabet, Part B is the practical winner; Part C is the answer when the interviewer asks to cut space.

Part D · Revision page

sol = Solution()
print(sol.checkInclusion("ab", "eidbaooo"))   # True
print(sol.checkInclusion("ab", "eidboaoo"))   # False
print(sol.checkInclusion("aa", "aa"))         # True
print(sol.checkInclusion("abc", "ab"))        # False
print(sol.checkInclusion("adc", "dcda"))      # True
print(sol.checkInclusion("ab", "bb"))         # False

Based on this video: Permutation in String · brute force, sliding window, space-optimised