567. Permutation in String

567

MediumSliding WindowHash map of character countsFixed-size window frequency match

Permutation in String

Given strings s1 and s2, return true if s2 contains a substring that is a permutation of s1 (a contiguous block with exactly s1's character counts), and false otherwise.

Open official problem prompt ↗

In plain English

Decide whether some contiguous slice of s2 is an exact rearrangement of s1.

Picture it like this

You carry a fixed set of Scrabble tiles (s1) and drag a window of that many slots along a longer rack (s2). You are happy the instant the tiles in the window are exactly your set, in any order.

Example

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Why: s2 contains the substring "ba" (indices 3-4), which is a permutation of "ab".

Constraints

1 <= s1.length, s2.length <= 10^4s1 and s2 consist of lowercase English letters

Pattern lesson

See the pattern, then code

Fixed-size window frequency match

↗

Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. A permutation is just a reordering, so only character frequencies matter. Slide a window of width len(s1) over s2 and compare counts; return true the moment they match.

New words, made simpleKnow these before the algorithm

Permutation: A rearrangement using exactly the same characters and counts.
Window map: The live character counts of the current slice.
Early exit: Returning as soon as the first matching window is found, since existence is all that is asked.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Check every permutation of s1

Factorial blowup; hopeless beyond tiny s1.

Generate all permutations of s1 and search each in s2.

Time O(m! * n)Space O(m)

Sort each candidate window

Re-sorting overlapping windows wastes work.

Sort every length-m window of s2 and compare to sorted s1.

Time O(n * m log m)Space O(m)

Best choiceIncremental count window

Constant work per position and a constant-size equality check.

Maintain window counts, add/remove one char per step, compare 26-entry maps.

Time O(n)Space O(1)

The rule we keep true

Invariant

For i >= k-1 the window map equals the counts of s2[i-k+1 .. i]; a map equal to need means that exact slice is a permutation of s1.

Why this is correct

Reasoning

Two strings are permutations of each other exactly when their character counts match. The window maintains those counts precisely (deleting zeros), so the first equality with need is a genuine permutation, and if the loop finishes with none, no window can match.

The algorithm in three movesSay these aloud before coding

1Build the frequency map of s1 and an empty window map

need = {a:1, b:1}

2Add each entering character on the right

window at [2..3] 'db' -> {d:1,b:1} no match

3Once the window exceeds len(s1), remove the character leaving on the left (delete zero entries)

window at [3..4] 'ba' -> {b:1,a:1} == need -> return true

4Return true if the window map ever equals s1's map; otherwise false after the loop

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readch='i'

2 · AskWindow full yet?

3 · Update statewindow={e:1,i:1}

4 · ResultNo match; window width now 2.

Key takeaway

The width-2 window 'ba' at indices 3-4 matches the target counts of 'ab'.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 5-6Length guard
If s1 is longer than s2, no window can fit, so return false immediately.
2
Lines 11-12Extend right
Count the entering character.
3
Lines 13-17Contract left
When the window grows past k, remove the outgoing character and delete zero counts to keep equality exact.
4
Lines 18-20Match check and exit
Return true at the first equal window; false only after scanning everything.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

s1 longer than s2 -> false
s1 equals s2 -> true
match sitting at the very end of s2
repeated letters in s1 such as 'aa'

Common beginner mistakes

Not deleting zero-count keys, breaking Counter equality
Removing the left character at the wrong step (should trigger when width exceeds k)
Returning based on containment of characters rather than exact counts (would wrongly accept extra copies)
Comparing full Counters rebuilt each step, losing linearity

Check your understanding

How does this problem differ from Find All Anagrams (438), and how does that change the loop?

PyPython 3 · solution.py

Optimal

1from collections import Counter23class Solution:4    def checkInclusion(self, s1: str, s2: str) -> bool:5        if len(s1) > len(s2):6            return False7        need = Counter(s1)8        window: Counter[str] = Counter()9        k = len(s1)10        for i, ch in enumerate(s2):11            window[ch] += 112            if i >= k:13                left = s2[i - k]14                window[left] -= 115                if window[left] == 0:16                    del window[left]17            if window == need:18                return True19        return False

Time complexityO(n)Optimized

Space complexityO(1)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

MicrosoftAmazonGoogle

Permutation in String

Permutation in String

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Sliding Window