#!/bin/env python
# -*- coding: utf-8 -*-

"""

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").


示例2:

输入: s1= "ab" s2 = "eidboaoo"
输出: False


注意:

输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间

"""


def find(s1, s2):
    from collections import Counter
    s1_len, s2_len = len(s1), len(s2)
    count = s1_len
    s1Char = Counter(s1)

    for i in range(s2_len):
        if s1Char[s2[i]] >= 1:
            count -= 1
        s1Char[s2[i]] -= 1
        if i >= s1_len:
            if s1Char[s2[i - s1_len]] >= 0:
                count += 1
            s1Char[s2[i - s1_len]] += 1
        if count == 0:
            return True

    return False


print find("ab", "eidbaooo")
print find("ab", "eidboaoo")
