class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_to_index = dict([(num, i) for i, num in enumerate(nums)])
        for i, num in enumerate(nums):
            expected_num_index = num_to_index.get(target-num)
            if expected_num_index and expected_num_index > i:
                return [i, expected_num_index]
        return []

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self) -> None:
        self.good_node_cnt = 0

    def goodNodes(self, root: TreeNode) -> int:
        self.good_node_cnt = 0
        self.solve_good_node_cnt(root, float('-INF'))
        return self.good_node_cnt
    
    def solve_good_node_cnt(self, root, max_val):
        if not root:
            return

        if root.val >= max_val:
            self.good_node_cnt += 1
            max_val = root.val
            
        self.solve_good_node_cnt(root.left, max_val)
        self.solve_good_node_cnt(root.right, max_val)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        s_len = len(s)
        ans = 0
        start = 0
        end = 0
        visited_char_set = set()
        for start in range(s_len):
            end = max(end, start)
            visited_char_set.add(s[start])

            while end + 1 < s_len and s[end + 1] not in visited_char_set:
                visited_char_set.add(s[end + 1])
                end += 1
            ans = max(ans, end - start + 1)

            visited_char_set.remove(s[start])
        return ans

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = nums[0]
        pre_max_sum = 0
        for num in nums:
            pre_max_sum = max(pre_max_sum + num, num)
            ans = max(pre_max_sum, ans)
        return ans

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ret = ''

        for i in range(0, len(s)):
            s1 = self.get_palindrome(s, i, i)
            s2 = self.get_palindrome(s, i, i+1)
            
            if len(s1) > len(ret):
                ret = s1
            if len(s2) > len(ret):
                ret = s2

        return ret

    def get_palindrome(self, s, left_index, right_index):
        ret = ''
        
        while left_index >= 0 and right_index < len(s) and s[left_index] == s[right_index]:
            ret = s[left_index: right_index + 1]
            left_index -= 1
            right_index += 1

        return ret