# Python, Simple with Explanation

• For each `window` representing a substring of `s2` of length `len(s1)`, we want to check if the count of the window is equal to the count of `s1`. Here, the count of a string is the list of: [the number of `a`'s it has, the number of `b`'s,... , the number of `z`'s.]

We can maintain the window by deleting the value of s2[i - len(s1)] when it gets larger than `len(s1)`. After, we only need to check if it is equal to the target. Working with list values of [0, 1,..., 25] instead of 'a'-'z' makes it easier to count later.

``````def checkInclusion(self, s1, s2):
A = [ord(x) - ord('a') for x in s1]
B = [ord(x) - ord('a') for x in s2]

target = [0] * 26
for x in A:
target[x] += 1

window = [0] * 26
for i, x in enumerate(B):
window[x] += 1
if i >= len(A):
window[B[i - len(A)]] -= 1
if window == target:
return True
return False
``````

• The fourth line from bottom should be:

``````window[B[i - len(A)]] -= 1
``````

• My rewrite:

``````class Solution(object):
def checkInclusion(self, s1, s2):
from string import lowercase
from copy import deepcopy
s1_counter = collections.defaultdict(int, {i:0 for i in lowercase})
s2_window_counter = deepcopy(s1_counter)
s1_counter.update(collections.Counter(s1))
s2_window_counter.update(collections.Counter(s2[:len(s1)]))
if s1_counter == s2_window_counter: return True
for i in range(len(s1), len(s2)):
s2_window_counter[s2[i]] += 1
s2_window_counter[s2[i - len(s1)]] -= 1
if s1_counter == s2_window_counter:
return True
return False
``````

• Like the cleverness of how you're dealing with maintaining the window, but this will be slower than just maintaining a dict of counts and just dealing with left and right end points. They will be asymptotically the same but the C (constant) factor here will be relatively big.

• @Ellest I'm not sure what you mean, are you referring to a solution like this? Initially I had a dict of counts as you suggested, but I checked dict1 == dict2 and it TLE'd on the contest. We need to manage also the non-zeroness in constant time.

``````def checkInclusion(self, s1, s2):
A = [ord(x) - ord('a') for x in s1]
B = [ord(x) - ord('a') for x in s2]

count = [0] * 26
for x in A:
count[x] -= 1
self.nonzero = sum(x != 0 for x in count)

def update(char, delta):
count[char] += delta
if count[char] == 0:
self.nonzero -= 1
elif count[char] == delta:
self.nonzero += 1

for i, x in enumerate(B):
update(x, 1)
if i >= len(A):
update(B[i - len(A)], -1)

if self.nonzero == 0:
return True
return False
``````

• @awice
You only need to keep track of a single dictionary of counts. Here's my solution:

``````    def checkInclusion(self, s1, s2):
if not s1: return True
letters = collections.Counter(s1)
lCnt, j = len(s1), 0
for i in range(len(s2)):
if s2[i] not in letters or letters[s2[i]] == 0 : # DNE or depleted
while j < i and s2[j] != s2[i]:
letters[s2[j]] += 1; j += 1
if s2[j] in letters: letters[s2[j]] += 1 # if in char map
j += 1
elif i-j+1 == lCnt: return True
if s2[i] in letters: letters[s2[i]] -= 1
return False
``````

Since we're putting back used characters when an invalid condition is met (non-existent char or char that has been depleted) we can assume that our count dict will at most contain counts we started with. Thus we just need to check if our current window size matches the length of s1 in order to validate the match.

• Just use a Counter:

``````def checkInclusion(self, s1, s2):
from collections import Counter
m, n = len(s1), len(s2)
cur, target = Counter(s2[:m]), Counter(s1)
if target == cur: return True
for i in range(n-m):
cur[s2[i]] -= 1
cur[s2[i+m]] += 1
cur += Counter()
if cur == target: return True
return False``````

• @lee215
Counters are basically dictionaries, are they not? Using a counter will have the same issue as using an array of size 26 as you'd be doing 26 comparisons each time in the worst case(in the case you have all letters of the alphabet present). I wanted to avoid doing just that with keeping my maintaining my window with an invariant. Yes, you can argue 26 is just a constant factor so it doesn't matter, but it just seemed unnecessary to me. Unless you're telling me that comparison between Counters are done by some how hashing the two object and comparing just the hash, iterating over the dict is unavoidable.

• @lee215 Just a little variation idea for the loop:

``````        for enter, leave in zip(s2[m:], s2):
cur[leave] -= 1
cur[enter] += 1
``````

• @Ellest
I didn't keep the key with value 0. The length of dictionary is not 26 in most of cases.

• @lee215
I said it's 26 in the worst case. Like I said I just thought there is a lot of unnecessary comparisons needed to be made when using a counter.

• good solution, here is a more compact version:

``````def checkInclusion(self, s1, s2):
l1 = [0]*26
l2 = [0]*26
for x in s1:
l1[ord(x) - ord('a')] += 1

for i in xrange(len(s2)):
l2[ord(s2[i]) - ord('a')] += 1
if i >= len(s1):
l2[ord(s2[i-len(s1)]) - ord('a')] -= 1
if l1 == l2:
return True
return False
``````

• cur += Counter()

Hey Lee, can you tell what is "cur += Counter()" about? why is this needed?

• @sha256pki
It will remove all keys with value zero and negative.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.