Does any window of s2 hold exactly the letters of s1? Slide a fixed-size window and keep 26 letter counts in step, one letter in and one out, so every check is O(1) and the whole scan is O(n).
▼The problem
LeetCode 567 (Medium). Given strings s1 and s2, return true if s2 contains a permutation of s1: some substring of s2 of length len(s1) with exactly the same letter counts (lowercase English letters).
Examples (LeetCode's): s1 = "ab", s2 = "eidbaooo" → true ("ba", frames 3-4; the walkthrough example); s1 = "ab", s2 = "eidboaoo" → false (its windows are ei id db bo oa ao oo; the b and a are split by an o).
The solution
def checkInclusion(s1, s2):
m = len(s1)
if m > len(s2):
return False
need = [0] * 26
have = [0] * 26
for c in s1:
need[ord(c) - 97] += 1
for i, c in enumerate(s2):
have[ord(c) - 97] += 1
if i >= m:
have[ord(s2[i - m]) - 97] -= 1
if have == need:
return True
return FalseTranscript
Permutation in String. Given two strings, return true if the second contains a permutation of the first: the same letters, in any order, side by side.
Take A, B, and E, I, D, B, A, O, O, O. B, A sit together, a reordering of A, B, so it's true. In E, I, D, B, O, A, O, O, the B and A are split up: false.
The naive way tries every ordering of the first string and searches for each. With m letters, that's m factorial orderings: ten letters make over three million. Sorting every window still repeats work.
The key: a permutation just has the same letter counts. So count the first string. Then slide a window of exactly that length along the second, counting its letters. Each step, one letter enters on the right and one leaves on the left: two updates. When the counts match, we've found one.
In code, count the first string. For each letter of the second, add it, and once the window is too long, remove the letter that fell out. If the two count lists are equal, return true.
Let's run it. The window fills with E, I: no match. Slide: D enters, E leaves. B enters, I leaves: D, B, still no. A enters, D leaves: B, A. One A, one B: a match! True.
Each letter enters and leaves once, and comparing twenty six counts is constant work: order n time. Only twenty six counts are kept: order one space.
Count the first string, slide a fixed window, compare. That's Permutation in String.