from collections import defaultdict

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        if len(points) <= 1: return 0
        graph = {}
        connection = defaultdict(int)
        for i, (idx1, idx2) in enumerate(points):
            graph[i] = {i}
            for j, (pos1, pos2) in enumerate(points):
                if j <= i: continue
                value = abs(idx1-pos1) + abs(idx2-pos2)
                connection[(i, j)] = value
        sorted_conn = sorted(connection.items(), key=lambda x: x[1], reverse=False)
        res = 0
        for pos, val in sorted_conn:
            if len(graph[pos[0]].intersection(graph[pos[1]]))==0:
                union_set = graph[pos[0]].union(graph[pos[1]])
                for pt in union_set:
                    graph[pt] = union_set
                res += connection[(pos[0], pos[1])]
        return res

from collections import defaultdict

class Solution:
    def __init__(self):
        self.res = ""
        self.dict = defaultdict()
    
    def isPalindrome(self, s, start, end):
        if (start, end) in self.dict.keys():
            return self.dict[(start, end)]
        s_ = s[start:end]
        if len(s_) == 1: return True
        left = 0
        right = len(s_) - 1
        while left<=right and s_[left] == s_[right]:
            left += 1
            right -= 1
        if left - right == 1 or left - right == 2:
            self.dict[(start, end)] = True
            return True
        else:
            self.dict[(start, end)] = False
            return False
    
    def longestPalindrome(self, s: str) -> str:
        res = ""
        self.longestPalindromeHelper(s, 0, len(s))
        return self.res
        
    def longestPalindromeHelper(self, s, start, end):
        if not self.isPalindrome(s, start, end):
            self.longestPalindromeHelper(s, start+1, end)
            self.longestPalindromeHelper(s, start, end-1)
        else:
            if end-start > len(self.res):
                self.res = s[start:end]