Permutation in String (LeetCode 567)

The problem

You get two strings s1 and s2. Return True if some contiguous piece of s2 is a permutation of s1, that is, it uses exactly the same letters the same number of times, in any order.

Input:  s1 = "ab", s2 = "eidbaooo"
Output: True

The substring "ba" at indices 3 to 4 of s2 is a rearrangement of "ab".

How to think about it

Start with brute force. Generate every permutation of s1 and search for each in s2. With m = len(s1), there are m! permutations, which explodes immediately. A better brute force checks each substring of s2 of length m by sorting it and comparing with sorted s1: O(n · m log m).

Reframe “permutation” as “same counts”. Two strings are permutations of each other exactly when their character counts match. Order doesn’t matter at all. So the question becomes: is there a window of length m in s2 whose letter counts equal those of s1?

The key insight: the window has a fixed size, so slide it. Moving the window one step to the right adds one character on the right and removes one on the left. Update the count map with those two changes instead of recounting the whole window. Then compare with s1’s counts.

Which pattern is this? A fixed-size sliding window over a frequency map. The tell is “substring that is an anagram/permutation of a given string”: the length is fixed by the pattern.

Approach

1. If s1 is longer than s2, return False.
2. Build need = Counter(s1) and win = Counter of the first m characters of s2. If equal, return True.
3. For each i from m to the end of s2: add s2[i] to win, and decrement the outgoing character s2[i - m], deleting it from win when its count reaches 0.
4. If win == need, return True.
5. If no window matched, return False.

Deleting zero-count keys matters: Counter equality in older Python versions treats a key with count 0 as different from a missing key.

Solution

from collections import Counter

def check_inclusion(s1, s2):
    if len(s1) > len(s2): return False
    need = Counter(s1); win = Counter(s2[:len(s1)])   # first window
    if win == need: return True
    for i in range(len(s1), len(s2)):
        win[s2[i]] += 1                                # incoming char
        left = s2[i-len(s1)]
        win[left] -= 1                                 # outgoing char
        if win[left] == 0: del win[left]               # keep the maps comparable
        if win == need: return True
    return False
# check_inclusion("ab", "eidbaooo") -> True

Dry run

On s1 = "ab", s2 = "eidbaooo", so need = {a: 1, b: 1} and the window length is 2:

The function returns True at i = 4.

Complexity

• Time: O(n). Each slide is O(1) to update, and comparing two maps with at most 26 keys is O(26). So O(26·n) = O(n) overall, with n = len(s2).
• Space: O(26) = O(1). Two small count maps.

Edge cases and pitfalls

• s1 longer than s2 can’t fit, so return False before slicing.
• s1 == s2 matches on the very first window.
• Leaving zero counts in the map. Without the del, the maps may compare unequal even when the real counts match (older Pythons and many other languages).
• Sorting each window is correct but O(m log m) per step.
• A faster variant keeps a matches counter of how many of the 26 letters currently agree, giving strict O(1) per step. Mention it if asked to optimise further.

Related problems

• Find All Anagrams in a String (LeetCode 438): the same window, collecting every match instead of stopping at the first.
• Valid Anagram (LeetCode 242): the “same counts” check on its own.
• Minimum Window Substring (LeetCode 76): the variable-size version, where the window must merely contain the counts.