# burte force
#  - time: O(n^3) # n to check a sub-str being a palindrome or not, n^2 to chekc all possible sub-str
#  - space: O(1)
# - Get every possible substring (O(n^2)), and check whether it is a palindrome (O(n))
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        res, resLen = "", 0

        for i in range(len(s)):
            for j in range(i, len(s)):
                l, r = i, j
                while l < r and s[l] == s[r]:
                    l += 1
                    r -= 1

                # l >= r 以判断 l 和 r 是否相遇了，如果相遇了，说明 s[i:j+1] 为 palindrome
                if l >= r and resLen < (j - i + 1):
                    res = s[i: j + 1]
                    resLen = j - i + 1
        return res
      
# 双指针
#  - time: O(n^2)
#  - space: O(1)  
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        longest_len = 0
        res = ""
        for i in range(len(s)):
            # odd, e.g., cbc in cbc
            l, r = i, i
            while l >= 0 and r <= len(s) - 1 and s[l] == s[r]:
                cur_len = r - l + 1  # 计算两指针包括的元素长度
                if cur_len > longest_len:
                    longest_len = cur_len
                    res = s[l:r + 1]
                l -= 1
                r += 1

            # even, e.g., bb in cbbc
            l, r = i, i + 1
            while l >= 0 and r <= len(s) - 1 and s[l] == s[r]:
                cur_len = r - l + 1  # 计算两指针包括的元素长度
                if cur_len > longest_len:
                    longest_len = cur_len
                    res = s[l:r + 1]
                l -= 1
                r += 1

        return res

# ??  
# Manacher's Algorithm
#  - time: O(n)
#  - space: O(1)  
    def longestPalindrome(self, s: str) -> str:
        def manacher(s):
            t = '#' + '#'.join(s) + '#'
            n = len(t)
            p = [0] * n
            l, r = 0, 0
            for i in range(n):
                p[i] = min(r - i, p[l + (r - i)]) if i < r else 0
                while (i + p[i] + 1 < n and i - p[i] - 1 >= 0 
                       and t[i + p[i] + 1] == t[i - p[i] - 1]):
                    p[i] += 1
                if i + p[i] > r:
                    l, r = i - p[i], i + p[i]
            return p
        
        p = manacher(s)
        resLen, center_idx = max((v, i) for i, v in enumerate(p))
        resIdx = (center_idx - resLen) // 2
        return s[resIdx : resIdx + resLen]

# solution - intuitive way
# - time: O(n)
# - space: O(n)
   def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        newStr = ""
        for c in s:
            if c.isalnum():
                newStr += c.lower()

        l, r = 0, len(newStr) - 1
        while l < r:
            if newStr[l] != newStr[r]:
                return False
            l += 1
            r -= 1
        return True
      
# solution 左右指针（双指针）
# - time: O(n)
# - space: O(1)
def isPalindrome(self, s):
		"""
		:type s: str
		:rtype: bool
		"""
		i, j = 0, len(s) - 1
		while i < j:
			left = s[i]
			right = s[j]
			if not left.isalnum():
				i += 1
				continue
			if not right.isalnum():
				j -= 1
				continue
			if left.lower() != right.lower():
				return False
			i += 1
			j -= 1
			
		return True
  
# solution 左右指针（双指针）- 更优雅的写法（本质逻辑没区别）
# - time: O(n)
# - space: O(1)
    def isPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r -= 1
            if s[l].lower() != s[r].lower():
                return False
            l += 1
            r -= 1
        return True
      
def alphaNum(self, c):
  return (ord('A') <= ord(c) <= ord('Z')) or (ord('a') <= ord(c) <= ord('z')) or ord('0') <= ord(c) <= ord('9')

# backtracking

	def longestPalindrome(self, s: str) -> int:
		m = {}
		for char in s:
			if char in m:
				m[char] = m[char] + 1
			else:
				m[char] = 1

		res = 0
		for v in m.values():
			if res & 1 == 1 and v & 1 == 1:
				v -= 1
			res += v

		return res

# brute force 
# - time: O(n2)
# - space: O(n)

# solution 左右指针（双指针）
# - time: O(n)
# - space: O(1)
   def validPalindrome(self, s):
        """
        :type s: str
        :rtype: bool
        """
        return self.validPalindromeWithDelete(s,True)

    def validPalindromeWithDelete(self, s, canDelete):
        l, r = 0, len(s) - 1
        while l < r:
            while l < r and not s[l].isalnum():
                l += 1
            while l < r and not s[r].isalnum():
                r += 1

            if s[l] != s[r]:
                if not canDelete:
                    return False
                else:
                    return self.validPalindromeWithDelete(s[l + 1:r + 1], False) or self.validPalindromeWithDelete(
                        s[l:r], False)
            l += 1
            r -= 1

        return True