class Solution:
    """
    @param: nums: a sorted integer array
    @param: lower: An integer
    @param: upper: An integer
    @return: a list of its missing ranges
    """
    
    
    def helper(self, left_point, right_point):
        if left_point == right_point:
            return str(left_point)
        else:
            return str(left_point) + "->" + str(right_point)
        
    
    
    def findMissingRanges(self, nums, lower, upper):
        # write your code here
        ans = []
        if len(nums) == 0:
            ans.append(self.helper(lower, upper))
            return ans
        pre_point = lower - 1
        for point in nums:
            if pre_point != point and pre_point + 1 != point:
                ans.append(self.helper(pre_point + 1, point - 1))
            pre_point = point
        if nums[-1] < upper:
            ans.append(self.helper(nums[-1] + 1, upper))
        return ans

from collections import defaultdict
class Solution:

    def canFinish(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """

        # Prepare the graph
        adj_list = defaultdict(list)
        indegree = {}
        for dest, src in prerequisites:
            adj_list[src].append(dest)

            # Record each node's in-degree
            indegree[dest] = indegree.get(dest, 0) + 1

        # Queue for maintainig list of nodes that have 0 in-degree
        zero_indegree_queue = [k for k in range(numCourses) if k not in indegree]

        topological_sorted_order = []

        # Until there are nodes in the Q
        while zero_indegree_queue:

            # Pop one node with 0 in-degree
            vertex = zero_indegree_queue.pop(0)
            topological_sorted_order.append(vertex)

            # Reduce in-degree for all the neighbors
            if vertex in adj_list:
                for neighbor in adj_list[vertex]:
                    indegree[neighbor] -= 1

                    # Add neighbor to Q if in-degree becomes 0
                    if indegree[neighbor] == 0:
                        zero_indegree_queue.append(neighbor)

        return len(topological_sorted_order) == numCourses

from collections import defaultdict
class Solution:
    
    WHITE = 1
    GRAY = 2
    BLACK = 3
    
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        
        topological_sorted_order = []
        
        adj_list = defaultdict(list)
         
        for des, src in prerequisites:
            adj_list[src].append(des)
            
        is_possible = True
        
        color = {k: Solution.WHITE for k in range(numCourses)}

        def dfs(node):
            nonlocal is_possible
            
            if not is_possible:
                return
            
            color[node] = Solution.GRAY
            
            if node in adj_list:
                for neighbor in adj_list[node]:
                    if color[neighbor] == Solution.WHITE:
                        dfs(neighbor)
                    elif color[neighbor] == Solution.GRAY:
                        is_possible = False
                        
            color[node] = Solution.BLACK
            topological_sorted_order.append(node)
            
        
        for course in range(numCourses):
            if color[course] == Solution.WHITE:
                dfs(course)
        
        return topological_sorted_order[::-1] if is_possible else []
                

from collections import defaultdict
class Solution:

    def findOrder(self, numCourses, prerequisites):
        """
        :type numCourses: int
        :type prerequisites: List[List[int]]
        :rtype: List[int]
        """

        # Prepare the graph
        adj_list = defaultdict(list)
        indegree = {}
        for dest, src in prerequisites:
            adj_list[src].append(dest)

            # Record each node's in-degree
            indegree[dest] = indegree.get(dest, 0) + 1

        # Queue for maintainig list of nodes that have 0 in-degree
        zero_indegree_queue = [k for k in range(numCourses) if k not in indegree]

        topological_sorted_order = []

        # Until there are nodes in the Q
        while zero_indegree_queue:

            # Pop one node with 0 in-degree
            vertex = zero_indegree_queue.pop(0)
            topological_sorted_order.append(vertex)

            # Reduce in-degree for all the neighbors
            if vertex in adj_list:
                for neighbor in adj_list[vertex]:
                    indegree[neighbor] -= 1

                    # Add neighbor to Q if in-degree becomes 0
                    if indegree[neighbor] == 0:
                        zero_indegree_queue.append(neighbor)

        return topological_sorted_order if len(topological_sorted_order) == numCourses else []

class Solution:
    """
    @param nums: a list of integers.
    @param k: length of window.
    @return: the sum of the element inside the window at each moving.
    """
    def winSum(self, nums, k):
        # write your code here
        ans = []
        
        if len(nums) == 0 or len(nums) < k or k <= 0: return ans
        
        sum = 0
        
        for i in range(k):
            sum += nums[i]
            
        ans.append(sum)
            
        
        for i in range(k, len(nums),):
            sum -= nums[i - k]
            sum += nums[i]
            ans.append(sum)
            
        return ans

class Solution:
    """
    @param nums: a list of integers.
    @param k: length of window.
    @return: the sum of the element inside the window at each moving.
    """
    def winSum(self, nums, k):
        # write your code here
        n = len(nums)
        if n < k or k <= 0:
            return []
        sums = [0] * (n - k + 1)
        for i in range(k):
            sums[0] += nums[i];

        for i in range(1, n - k + 1):
            sums[i] = sums[i - 1] - nums[i - 1] + nums[i + k - 1]

        return sums

class Solution:
    def isRectangleOverlap(self, rec1: List[int], rec2: List[int]) -> bool:
       
       return not (rec2[0] >= rec1[2] or rec2[2] <= rec1[0] or rec2[3] <= rec1[1] or rec2[1] >= rec1[3])

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: the root of binary tree
    @return: the maximum weight node
    """
        

    def findSubtree(self, root):
        # write your code here
        return self.findSubtreeHelper(root)[2]
        
    def findSubtreeHelper(self, root):
        
        if root is None:
            
            return 0, 0, None 
            
        left_max_sum, left_sum, left_root = self.findSubtreeHelper(root.left)
        right_max_sum, right_sum, right_root = self.findSubtreeHelper(root.right)
        
        curt_sum =  left_sum + right_sum + root.val
        max_sum = max(left_max_sum, right_max_sum, curt_sum)
        
        if max_sum == left_max_sum:
            
            max_root = left_root
            
        elif max_sum == right_max_sum:
            
            max_root = right_root
            
        else:
            
            max_root = root 
            
        return max_sum, curt_sum, max_root

class Solution:
    def longestPalindrome(self, s: str) -> int:
   
        if s is None:
            return 0
        ans = 0
        di = collections.Counter(s)
        center = False
        
        for st in di.keys():
            if di[st] % 2 == 0:
                ans += di[st]
            else:
                center = True
                ans += di[st] // 2 * 2
        if center:
            ans += 1
            
        return ans

 class Solution:
    """
    @param s: a string which consists of lowercase or uppercase letters
    @return: the length of the longest palindromes that can be built
    """
    def longestPalindrome(self, s):
        # write your code here
        if s is None:
            return 0

        hashTable = set()
        ans = 0
        for ch in s:
            if ch in hashTable:
                hashTable.remove(ch)
                ans += 2
            else:
                hashTable.add(ch)
                    
        if hashTable:
            ans += 1
       
        return ans