# solution 1 - 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()
  

# solution 2 - 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()

# solution 1 - hashmap - 我的解法
# time: max(O(s), O(t))
# space: O(1), 因为只有26个小写字母
def isAnagram(self, s, t):
		if len(s) != len(t):
			return False

		m = {}
		for char in s:
			m[char] = m.get(char, 0) + 1

		for char in t:
			if char not in m:
				return False

			m[char] -= 1
			if m[char] == 0:
				del m[char]

		return len(m) == 0
  

# solution 2 - hashmap - Neetcode（和上面没有本质区别）
# time: O(s)
# space: O(1), 因为只有26个小写字母
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return False

        countS, countT = {}, {}

        for i in range(len(s)):
            countS[s[i]] = 1 + countS.get(s[i], 0)
            countT[t[i]] = 1 + countT.get(t[i], 0)
        return countS == countT # time: O(26)

# solution 3 - sort      
# time: O(nlogn)，其中 n 为 s 的长度。排序的时间复杂度为 O(nlogn)，比较两个字符串是否相等时间复杂度为 O(n)，因此总体时间复杂度为 O(nlogn)
# space: O(1) or O(n), depending on the sorting algorithm
	def isAnagram(self, s, t):
		if len(s) != len(t):
			return False

		sorted_s = sorted(s.lower()) # time:O(nlogn)
		sorted_t = sorted(t.lower())

		# Compare the sorted lists of letters
		return sorted_s == sorted_t # time: O(n)

# solution - sliding window 
# - time: O(s)
# - space: O1）
	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(s)
			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)
			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(p)
				res.append(l)
		return res