LeetCode #567 Medium

Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1 as a contiguous substring.

stringsliding-windowhash-table

02

Intuition

💡

The trap is re-sorting or re-counting the whole window's characters at every slide, which is O(n * k log k) or worse -- it throws away work you already did on the previous window. The window here is a FIXED width, exactly len(s1), so as it slides by one position exactly one character enters on the right and exactly one leaves on the left. Update two running counts instead of recomputing from scratch: bump the entering character up, bump the leaving character down. You can go one step further and avoid even comparing 26 count buckets every time -- keep a single matches counter that tracks how many characters currently have the exact count s1 needs, and only increment or decrement it when a bump causes a count to enter or leave equality with the target. Then checking whether the window is a permutation is just matches == number of needed keys, an O(1) comparison instead of a scan.

03

Approach

1

Build the target count map once

Count the letters of s1 into a need map. This never changes for the rest of the algorithm -- it's the fixed target every window is compared against.

2

Slide a fixed-width window with running counts

Walk s2 with a right pointer. Add the entering character to a have map; once the window has grown past width len(s1), also remove the character leaving on the left. Never rebuild have from scratch.

3

Track a matches counter for O(1) comparison

Whenever a bump makes a character's count in have equal its count in need, increment matches; whenever a bump moves a count away from that equality, decrement matches. The window is a permutation of s1 exactly when matches equals the number of distinct keys in need.

04

Solution & live demo

python

▶1class Solution:
▶2    def checkInclusion(self, s1, s2):
▶3        from collections import Counter
▶4        k = len(s1)
▶5        if k > len(s2):
▶6            return False
▶7        need = Counter(s1)
▶8        have = Counter()
▶9        matches = 0
▶10        need_keys = len(need)
▶11        for r in range(len(s2)):
▶12            have[s2[r]] += 1
▶13            if have[s2[r]] == need.get(s2[r], 0):
▶14                matches += 1
▶15            elif have[s2[r]] == need.get(s2[r], -1) + 1:
▶16                pass
▶17            if r >= k:
▶18                left_ch = s2[r - k]
▶19                if have[left_ch] == need.get(left_ch, 0):
▶20                    matches -= 1
▶21                have[left_ch] -= 1
▶22            if r >= k - 1 and matches == need_keys:
▶23                return True
▶24        return False

05

Edge cases

s1 longer than s2

No window of that width fits in s2, so the loop never reaches full width and the answer is false; guard against this or let the loop naturally produce zero valid windows.

s1 and s2 are identical

The single full-width window is trivially a permutation of itself, so matches reaches the needed count on the last character processed.

Repeated characters in s1

The need map naturally holds counts greater than 1 for repeated letters; the matches-counter approach still works since equality is checked per distinct key, not per occurrence.

No permutation exists anywhere in s2

Every window's matches count stays below the needed total, and the function correctly returns false after scanning the whole string.

06

Complexity

Time

O(n)

Space

O(1)

n is len(s2); each character enters and leaves the window exactly once, and the count maps are bounded by the alphabet size (26 lowercase letters).