Workspace

Problem workspace

3 day streakD

Permutation in a String

MediumSliding WindowFixed windows

The challenge

Return true if any substring of s is a permutation of pattern; otherwise return false.

Strings contain lowercase English letters. The pattern is nonempty. Indices are zero-based.

Example

s = eidbaooo, pattern = ab → true, because ba appears at index 3.

Use the walkthrough below to inspect the input and each state change.

See Permutation check, step by step

Expand, shrink, and inspect the window state.

8 elements · zero-based indicespattern = ab
Sliding window over 8 elementsThe current window is empty. Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.Empty window · L = 0, R = -1e0i1d2b3a4o5o6o7
Current windowRecorded answerOutside window
Left
0
Right
-1
Length
0
Step 01 / 11

Start with an empty window

Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.

left = 0; right = −1

Answer so far

false
View exact input

Input: ["e","i","d","b","a","o","o","o"] · pattern = ab

Current window is empty.

Put it into code

Use the anagram frequency window, returning immediately at the first match. The function takes the source first and pattern second.

Indices are zero-based. C++ uses C++17 or later.

def contains_permutation(s, pattern):
    # Lowercase English letters; pattern is nonempty.
    need, window = [0] * 26, [0] * 26
    for char in pattern:
        need[ord(char) - ord('a')] += 1
    k = len(pattern)
    for right, char in enumerate(s):
        window[ord(char) - ord('a')] += 1
        if right >= k:
            window[ord(s[right - k]) - ord('a')] -= 1
        if right >= k - 1 and window == need:
            return True
    return False

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap