Problem statement

https://leetcode.com/problems/permutation-in-string/

Solution

Let us use sliding window, where we count frequencies of each letter. We can just remove old letter and add new one and check if frequencies are what we need in O(26) for each step, then we have O(26n) complexity, where n$ is length of string s2. We can do smarter if we also have num_to_correct variable which count number of letters for which we need to fix frequencies.

Complexity

Then time complexity will be O(n), space complexity is O(n) to keep A and B, which can be reduced to O(26) if we do it on the fly.

Code

class Solution:
    def checkInclusion(self, s1, s2):
        A = [ord(x) - ord('a') for x in s1]
        B = [ord(x) - ord('a') for x in s2]
        if len(A) > len(B): return False
    
        target = [0] * 26
        for i in range(len(A)):
            target[A[i]] -= 1
            target[B[i]] += 1
        
        num_to_correct = sum([i != 0 for i in target])
        if num_to_correct == 0: return True
            
        for i in range(len(A), len(B)):
            new_s = B[i]
            target[new_s] += 1
            if target[new_s] == 0: num_to_correct -= 1
            if target[new_s] == 1: num_to_correct += 1
                
            old_s = B[i - len(A)]
            target[old_s] -= 1
            if target[old_s] == -1: num_to_correct += 1
            if target[old_s] == 0: num_to_correct -= 1
                                
            if num_to_correct == 0: return True  
                    
        return False