Introduction

This problem asks whether some permutation of one string appears as a contiguous substring inside another string. The key insight is that you do not need to generate permutations at all. You only need to check whether any window of the right length has the same character counts.

Why Brute Force Is the Wrong Approach

If s1 has length m, then generating all permutations can explode factorially. That is far too slow even for modest input sizes.

Instead, treat the problem as a frequency-matching problem:

• count the characters in s1
• slide a window of length len(s1) across s2
• compare counts efficiently

If one window has exactly the same counts, then that window is a permutation of s1.

Sliding Window With Character Counts

For lowercase English letters, a fixed-size array works very well.

1def contains_permutation(s1: str, s2: str) -> bool:
2    if len(s1) > len(s2):
3        return False
4
5    target = [0] * 26
6    window = [0] * 26
7
8    def index(ch: str) -> int:
9        return ord(ch) - ord("a")
10
11    for ch in s1:
12        target[index(ch)] += 1
13
14    for ch in s2[:len(s1)]:
15        window[index(ch)] += 1
16
17    if window == target:
18        return True
19
20    left = 0
21    for right in range(len(s1), len(s2)):
22        window[index(s2[right])] += 1
23        window[index(s2[left])] -= 1
24        left += 1
25
26        if window == target:
27            return True
28
29    return False
30
31
32print(contains_permutation("ab", "eidbaooo"))
33print(contains_permutation("ab", "eidboaoo"))

This returns True for the first example because "ba" appears inside "eidbaooo", and False for the second.

How the Window Logic Works

Suppose s1 = "ab". Then every relevant substring of s2 must also have length 2.

You do not care about longer or shorter substrings because a permutation must use exactly the same characters as s1.

So the algorithm:

1. counts the characters in s1
2. counts the first window in s2
3. shifts the window one character at a time
4. updates counts by adding one character and removing one character

That update step is the reason the algorithm stays efficient. You do not rebuild the whole frequency map from scratch for every position.

Time and Space Complexity

If the alphabet is fixed, the approach is effectively linear in the length of s2.

• time complexity is O(n)
• space complexity is O(1) for fixed alphabet size

That is a huge improvement over generating permutations.

If the character set is larger or arbitrary, a dictionary-based approach may be more flexible, though the idea stays the same.

Dictionary Version for General Characters

If you do not want to assume lowercase English letters only, use dictionaries:

1from collections import Counter
2
3
4def contains_permutation_general(s1: str, s2: str) -> bool:
5    if len(s1) > len(s2):
6        return False
7
8    target = Counter(s1)
9    window = Counter(s2[:len(s1)])
10
11    if window == target:
12        return True
13
14    for i in range(len(s1), len(s2)):
15        window[s2[i]] += 1
16        left_char = s2[i - len(s1)]
17        window[left_char] -= 1
18
19        if window[left_char] == 0:
20            del window[left_char]
21
22        if window == target:
23            return True
24
25    return False

This version is a little heavier but works for more general input.

Think in Counts, Not Order

The subtle but important idea is that permutations care about frequency, not sequence order.

For example:

• '"abc"'
• '"bca"'
• '"cab"'

All share the same character counts. That is why a sliding frequency window works so well. Once the counts match, the current substring is a valid permutation no matter how the letters are arranged inside the window.

Common Pitfalls

The most common pitfall is trying to generate every permutation of s1. That makes the problem much slower than it needs to be.

Another mistake is forgetting the early exit when len(s1) > len(s2). In that case, success is impossible.

A third issue is rebuilding the frequency count from scratch for every window instead of updating it incrementally.

Finally, some solutions assume lowercase English letters without stating that assumption. If the input can contain arbitrary characters, use a dictionary-based approach instead of a fixed 26-slot array.

Summary

• You do not need to generate permutations to solve this problem.
• The efficient solution uses a sliding window and character-frequency comparison.
• If one window of length len(s1) matches the frequency counts of s1, a permutation exists in s2.
• Fixed-size arrays are fast for small known alphabets such as lowercase letters.
• Dictionary-based counting is more flexible when the character set is not restricted.