Example 1
ready- Input
s1 = "ab" s2 = "eidbaooo"- Expected
true- Why
- the window 'ba' uses one 'a' and one 'b'
Permutation in String
35 min · checkInclusion()mediumOpen in LeetCode #567 ↗
A shuffled word can hide inside a much longer string without keeping any of its original order.
A permutation is a rearrangement that uses every character exactly as many times as
before. Given lowercase strings s1 and s2, return true when some substring — a
contiguous stretch — of s2 is a permutation of s1. Otherwise, return false.
Another way to say it: the matching window must have the same character multiset,
meaning the same characters with the same frequencies. If s1 is longer than s2, no
such window can exist.
A few ground rules:
- Order inside the matching window doesn't matter.
- Repeated letters do matter: two copies must be matched by two copies.
- The window length is always exactly
s1.length.
Constraints
1 <= s1.length, s2.length <= 100_000s1ands2contain only lowercase English lettersathroughz.
Hints
Fix the window size
Any permutation of s1 has exactly s1.length characters. You never need to test
shorter or longer windows in s2.
Compare frequencies
Build 26 counts for s1. For a candidate window, build the same counts and compare
them. This works, but rebuilding for every starting position repeats a lot of work.
Update only two letters
When the window moves right by one position, one character leaves and one enters. Adjust those two counts and track how many of the 26 buckets still match.
Follow-up
Could you return the starting index of the first matching window while keeping the same time and space bounds?
Visible cases
Examples
Example 2
ready- Input
s1 = "ab" s2 = "eidboaoo"- Expected
false- Why
- no two-character window has both required letters
Example 3
ready- Input
s1 = "adc" s2 = "dcda"- Expected
true- Why
- the ending window 'cda' rearranges all three letters
Interview signal
Asked at
AmazonMicrosoftMeta
Recount every window
Every possible match has length len(s1). Build the target's 26 letter counts, then
recount each window of that length in s2 from scratch.
def check_inclusion(s1: str, s2: str) -> bool:
window_size = len(s1)
if window_size > len(s2):
return False
target = [0] * 26
for char in s1:
target[ord(char) - ord("a")] += 1
for start in range(len(s2) - window_size + 1):
window = [0] * 26
for index in range(start, start + window_size):
window[ord(s2[index]) - ord("a")] += 1
if window == target:
return True
return FalseLet m = len(s1) and n = len(s2). Time O(n · m), Space O(26).
Incremental counts
Keep a fixed sliding window — a contiguous range with constant length — over s2.
When it moves, only two counts change: the outgoing character loses one, and the incoming
character gains one.
Track matches, the number of letter buckets where the window count equals the target
count. A window is a permutation exactly when all 26 buckets match.
def check_inclusion(s1: str, s2: str) -> bool:
window_size = len(s1)
if window_size > len(s2):
return False
target = [0] * 26
window = [0] * 26
for char in s1:
target[ord(char) - ord("a")] += 1
for index in range(window_size):
window[ord(s2[index]) - ord("a")] += 1
matches = sum(target[i] == window[i] for i in range(26))
if matches == 26:
return True
for right in range(window_size, len(s2)):
outgoing = ord(s2[right - window_size]) - ord("a")
if window[outgoing] == target[outgoing]:
matches -= 1
window[outgoing] -= 1
if window[outgoing] == target[outgoing]:
matches += 1
incoming = ord(s2[right]) - ord("a")
if window[incoming] == target[incoming]:
matches -= 1
window[incoming] += 1
if window[incoming] == target[incoming]:
matches += 1
if matches == 26:
return True
return FalseBuilding the first window costs O(m); every later move does constant work. Time O(n + m), Space O(26).
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
true
Run: visible + custom · Submit: full suite