from typing import *


class Solution:
    def checkStrInclusion(self, s1: str, s2: str):
        """
        :param s1: 被包含的字符串
        :param s2: 较长的那个字符串
        :return: 如果s1的全排列可以包含在s2中，返回True，否则返回False
        """
        if len(s1) > len(s2):
            return False

        # 从状态数组判断两个字符串是否是包含关系
        def checkTwoS(a: List[int], b: List[int]) -> bool:
            for i in range(26):
                if a[i] != b[i]:
                    return False
            return True

        a, b = [0 for _ in range(26)], [0 for _ in range(26)]
        for i in range(len(s1)):
            a[ord(s1[i]) - ord('a')] += 1
            b[ord(s2[i]) - ord('a')] += 1

        # 维护长度为len(s2)的滑动窗口，一次遍历判断是否存在包含关系
        left, right = 0, len(s1)-1
        while right < len(s2):
            if checkTwoS(a, b):
                return True
            b[ord(s2[left]) - ord('a')] -= 1
            left += 1
            right += 1
            if right < len(s2):
                b[ord(s2[right]) - ord('a')] += 1
        return False


if __name__ == '__main__':
    s = Solution()
    print(s.checkStrInclusion('adfsafd', 'asdfasdf'))