# hashmap + sorting - myself
#  - time: O(N * max_char log max_char)
#  - space: O(n)
def groupAnagrams(self, strs):
		m = {}
		for str in strs:
			sortedStr = "".join(sorted(str))
			if sortedStr in m:
				m[sortedStr].append(str)
			else:
				m[sortedStr] = [str]

		return m.values()
  

# hashmap - myself
#  - time: O(n * max_char)
#  - space: O(n)
	def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
		m = {}
		for str in strs:  # time: O(n)
			curSign = [0] * 26
			for char in str:  # time: O(max_char)
				curSign[ord(char) - ord("a")] += 1  # ord("a") means the ASCII of "a"

			# because Python cannot use list as the keys of a list
			if tuple(curSign) in m:
				m[tuple(curSign)].append(str)
			else:
				m[tuple(curSign)] = [str]
		return m.values()

# hashmap
 - Time complexity: O(t+s)
 - Space complexity: O(1) # since we have at most 26 different characters.
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False

        m = {}
        for c in s:
            m[c] = 1 + m.get(c, 0)
        for c in t:
            if c not in m:
                return False
            if c in m:
                m[c] -= 1
                if m[c] == 0:
                    del m[c]
        return len(m) == 0
      
# hashmap2
 - Time complexity: O(t+s)
 - Space complexity: O(1) # since we have at most 26 different characters.
     def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False

        s_m = {}
        t_m = {}
        for i in range(len(s)):
            s_m[s[i]] = 1 + s_m.get(s[i], 0)
            t_m[t[i]] = 1 + t_m.get(t[i], 0)
        return s_m == t_m

# hashmap3
 - Time complexity: O(t+s)
 - Space complexity: O(1) # since we have at most 26 different characters.
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False

        m = [0] * 26
        for i in range(len(s)):
            m[ord(s[i]) - ord('a')] += 1
            m[ord(t[i]) - ord('a')] -= 1

        for n in m:
            if n != 0:
                return False
        return True
      
# sort      
 - Time complexity: O(slogs+tlogt)
 - Space complexity: O(s+t)/O(1)
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        if len(s) != len(t):
            return False
        return sorted(s) == sorted(t)

# sliding window + hashmap（写法1）
# - time: O(s)  # O(26*s)
# - space: O(1）# O(2*26)
	def findAnagrams(self, s: str, p: str) -> List[int]:
		if len(s) < len(p):
			return []

		# space: O(1), since at most 26 lowercase English letters
		pM = {}
		sM = {}
		for i in range(len(p)):  # time: O(p)
			pM[p[i]] = pM.get(p[i], 0) + 1
			sM[s[i]] = sM.get(s[i], 0) + 1

		res = []
		if pM == sM:
			res.append(0)

		l = 0
		for r in range(len(p), len(s)):  # time: O(s-p)
			sM[s[r]] = sM.get(s[r], 0) + 1
			sM[s[l]] -= 1
			if sM[s[l]] == 0:
				del sM[s[l]]
			l += 1
			if sM == pM:  # time: O(1)
				res.append(l)
		return res
  
# sliding window + sign（写法2）
# - time: O(s)  # O(26*s)
# - space: O(1) # O(2*26) 
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        if len(s) < len(p):
            return []

        pSign = [0] * 26
        windowSign = [0] * 26
        for i in range(len(p)):  # time: O(p)
            windowSign[ord(s[i]) - ord("a")] += 1
            pSign[ord(p[i]) - ord("a")] += 1

        res = []
        l = 0
        r = len(p) - 1
        while True:  # time:O(s)
            if pSign == windowSign:
                res.append(l)
            windowSign[ord(s[l]) - ord("a")] -= 1
            l += 1
            r += 1
            if r >= len(s):
                break
            windowSign[ord(s[r]) - ord("a")] += 1
        return res

# brute force
#  - time: O(n^3logn)
#  - space: O(n)
    def checkInclusion(self, s1: str, s2: str) -> bool:
        s1 = sorted(s1)

        for i in range(len(s2)):
            for j in range(i, len(s2)):
                subStr = s2[i : j + 1]
                subStr = sorted(subStr)
                if subStr == s1:
                    return True
        return False
      
# hashmap
#  - time: O(n*m) # O(26*n*m) 
#  - space: O(1)  # O(26)
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        count1 = {}
        for c in s1:
            count1[c] = count1.get(c, 0) + 1

        for i in range(len(s2)):
            count2 = {}
            for j in range(i, len(s2)):
                count2[s2[j]] = count2.get(s2[j], 0) + 1
                if count1.get(s2[j], 0) < count2[s2[j]]: # 出现了当前扫描的 s2 的 sub_str 中不存在于 s1 中，或者该元素在 s2 中出现的次数比在 s1 中出现的还多
                    break
                if count1.get(s2[j], 0) == count2[s2[j]]: # 没理解为什么
                    cur += 1
                if cur == need:
                    return True
        return False

# sliding window + hashmap(sign) - 需要 compare sign 
#  - time: O(n) # O(26n) 
#  - space: O(1)  # O(2*26)
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        if len(s1) > len(s2):
            return False

        sign1 = [0] * 26
        sign2 = [0] * 26
        for i in range(len(s1)):
            sign1[ord(s1[i]) - ord('a')] += 1
            sign2[ord(s2[i]) - ord('a')] += 1
        if sign1 == sign2:
            return True

        l = 0
        for r in range(len(s1), len(s2)):
            sign2[ord(s2[r]) - ord('a')] += 1
            sign2[ord(s2[l]) - ord('a')] -= 1
            l += 1
            if sign1 == sign2:
                return True
        return False
      
# sliding window - 不需要 compare sign
#  - time: O(n) # O(n) 
#  - space: O(1)  # O(2*26)
    def checkInclusion(self, s1: str, s2: str) -> bool:
        if len(s1) > len(s2):
            return False
        
        s1Count, s2Count = [0] * 26, [0] * 26
        for i in range(len(s1)):
            s1Count[ord(s1[i]) - ord('a')] += 1
            s2Count[ord(s2[i]) - ord('a')] += 1
        
        matches = 0
        for i in range(26):
            matches += (1 if s1Count[i] == s2Count[i] else 0)
        
        l = 0
        for r in range(len(s1), len(s2)):
            if matches == 26:
                return True
            
            index = ord(s2[r]) - ord('a')
            s2Count[index] += 1
            if s1Count[index] == s2Count[index]:
                matches += 1
            elif s1Count[index] + 1 == s2Count[index]:
                matches -= 1

            index = ord(s2[l]) - ord('a')
            s2Count[index] -= 1
            if s1Count[index] == s2Count[index]:
                matches += 1
            elif s1Count[index] - 1 == s2Count[index]:
                matches -= 1
            l += 1
        return matches == 26