Permutation in String

Check if a string contains a permutation of another by tracking character counts in a sliding window.

sliding-window two-pointers hash-map string

Given two strings `s1` and `s2`, return `True` if `s2` contains a permutation of `s1` as a contiguous substring. In other words, return `True` if one of `s1`'s permutations is the substring of `s2`. The function signature is: `def check_inclusion(s1: str, s2: str) -> bool:`.

A permutation of `s1` is any rearrangement of its characters. The substring in `s2` must be exactly the same length as `s1` and contain exactly the same characters with the same frequencies.

You must solve it with a sliding window of fixed length (window size = len(s1)) to achieve O(n) time, where n is the length of `s2`. You may assume the strings contain only lowercase English letters.

Constraints

`1 <= len(s1), len(s2) <= 10^4`
`s1` and `s2` consist of only lowercase English letters.
Expected time complexity: O(len(s1) + len(s2)), space O(1) (since alphabet size is constant).

Example

>>> check_inclusion("ab", "eidbaooo")
True
>>> check_inclusion("ab", "eidboaoo")
False
>>> check_inclusion("a", "ab")
True
>>> check_inclusion("abc", "bbbca")
True

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use an array of 26 integers to track character frequency differences.

Maintain a sliding window of length len(s1). When the window is exactly that length, compare the frequency arrays.

As the window slides, decrement the count of the character leaving and increment the count of the character entering.

Instead of comparing arrays each time, keep a variable `matches` that counts how many of the 26 letters have equal frequencies.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.