class Solution:
    def isPalindrome(self, x: int) -> bool:
        """
        Determine whether an integer is a palindrome.
        An integer is a palindrome when it reads the same backward as forward.
        :param x:
        :return:
        >>> solution = Solution()
        >>> solution.isPalindrome(121)
        True
        >>> solution.isPalindrome(-121)
        False
        >>> solution.isPalindrome(10)
        False
        """
        if x < 0:
            return False
        res, t = 0, x

        while t > 0:
            t, low_num = t // 10, t % 10
            res = res*10 + low_num
        return res == x

class Solution:
    def countAndSay(self, n: int) -> str:
        """
        The count-and-say sequence is the sequence of integers with the first five terms as following:
        
        1.     1
        2.     11
        3.     21
        4.     1211
        5.     111221
        1 is read off as "one 1" or 11.
        11 is read off as "two 1s" or 21.
        21 is read off as "one 2, then one 1" or 1211.
        
        Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit.
        
        Note: Each term of the sequence of integers will be represented as a string.
        :param n:
        :return:
        >>> solution = Solution()
        >>> solution.countAndSay(1)
        '1'
        >>> solution.countAndSay(4)
        '1211'
        """
        res = "1"
        import itertools
        for _ in range(n-1):
            res = ''.join((str(len(list(g))) + digit for digit, g in itertools.groupby(res)))
        return res

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        """
        Implement strStr().
        Return the index of the first occurrence of needle in haystack,
        or -1 if needle is not part of haystack.
        :param haystack:
        :param needle:
        :return:

        >>> solution = Solution()
        >>> solution.strStr("hello", "ll")
        2
        >>> solution.strStr("aaaaa", "bba")
        -1
        >>> solution.strStr("a", "a")
        0
        """
        if needle == "":
            return 0
        length = len(needle)
        for i in range(len(haystack)):
            if haystack[i: i+length] == needle:
                return i
        return -1

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        """
        Given two strings s and t , write a function to determine if t is an anagram of s.
        :param s:
        :param t:
        :return:
        >>> solution = Solution()
        >>> solution.isAnagram("anagram", "nagaram")
        True
        >>> solution.isAnagram("rat", "car")
        False
        """
        s_hash, t_hash = [0] * 26, [0]*26

        for c in s:
            s_hash[ord(c)-ord('a')] += 1

        for c in t:
            t_hash[ord(c)-ord('a')] += 1

        return s_hash == t_hash

class Solution:
    def simplifyPath(self, path: str) -> str:
        """
        Given an absolute path for a file (Unix-style), simplify it.
        Or in other words, convert it to the canonical path.
        In a UNIX-style file system, a period . refers to the current directory.
        Furthermore, a double period .. moves the directory up a level.
        For more information, see: Absolute path vs relative path in Linux/Unix
        Note that the returned canonical path must always begin with a slash /,
        and there must be only a single slash / between two directory names.
        The last directory name (if it exists) must not end with a trailing /.
        Also, the canonical path must be the shortest string representing the absolute path.

        :param path:
        :return:
        >>> solution = Solution()
        >>> solution.simplifyPath('/home/')
        '/home'
        >>> solution.simplifyPath('/../')
        '/'
        >>> solution.simplifyPath('/home//foo/')
        '/home/foo'
        >>> solution.simplifyPath('/a/./b/../../c/')
        '/c'
        >>> solution.simplifyPath('/a/../../b/../c//.//')
        '/c'
        >>> solution.simplifyPath('/a//b////c/d//././/..')
        '/a/b/c'
        """
        stack = []
        for p in path.split('/'):
            if p == '..':
                if stack:
                    stack.pop()
            elif p and p != '.':
                stack.append(p)

        return '/' + '/'.join(stack)

class Solution:
    def multiply(self, num1: str, num2: str) -> str:
        """
        Given two non-negative integers num1 and num2 represented as strings,
        return the product of num1 and num2, also represented as a string.
        Note:

        The length of both num1 and num2 is < 110.
        Both num1 and num2 contain only digits 0-9.
        Both num1 and num2 do not contain any leading zero, except the number 0 itself.
        You must not use any built-in BigInteger library or convert the inputs to integer directly.
        :param num1:
        :param num2:
        :return:
        >>> solution = Solution()
        >>> solution.multiply('2', '3')
        '6'
        >>> solution.multiply('123', '456')
        '56088'
        """
        if num1 == '0' or num2 == '0':
            return '0'
        num1 = [ord(c) - ord('0') for c in num1][::-1]
        num2 = [ord(c) - ord('0') for c in num2][::-1]
        ans = [0]*(len(num1)+len(num2))
        for i, n1 in enumerate(num1):
            for j, n2 in enumerate(num2):
                div, mod = divmod(ans[i+j] + n1*n2, 10)
                ans[i+j] = mod
                ans[i+j+1] += div
        pt = 0
        ans = ans[::-1]
        while pt < len(ans) and ans[pt] == 0:
            pt += 1
        return ''.join(map(str, ans[pt:]))

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        """
        Given an input string (s) and a pattern (p),
        implement regular expression matching with support for '.' and '*'.

        '.' Matches any single character.
        '*' Matches zero or more of the preceding element.
        The matching should cover the entire input string (not partial).

        Note:
        s could be empty and contains only lowercase letters a-z.
        p could be empty and contains only lowercase letters a-z, and characters like . or *.

        :param s:
        :param p:
        :return:

        >>> solution = Solution()
        >>> solution.isMatch('aa', 'a')
        False
        >>> solution.isMatch('aa', 'a*')
        True
        >>> solution.isMatch('aab', 'c*a*b')
        True
        >>> solution.isMatch('mississippi', 'mis*is*p*.')
        False
        >>> solution.isMatch('mississippi', 'mis*is*ip*.')
        True
        >>> solution.isMatch('ab', '.*c')
        False
        >>> solution.isMatch('aasdfasdfasdfasdfas', 'aasdf.*asdf.*asdf.*asdf.*s')
        True
        """
        dp = [[False for _ in range(len(p)+1)] for _ in range(len(s)+1)]
        dp[0][0] = True

        for j in range(1, len(p)+1):
            if j > 1 and p[j-1] == '*' and dp[0][j-2]:
                dp[0][j] = True

        for i in range(1, len(s)+1):
            for j in range(1, len(p)+1):
                if s[i-1] == p[j-1] or p[j-1] == '.':
                    dp[i][j] = dp[i-1][j-1]
                elif p[j-1] == '*':
                    if p[j-2] != s[i-1] and p[j-2] != '.':
                        dp[i][j] = dp[i][j-2]
                    elif p[j-2] == s[i-1] or p[j-2] == '.':
                        dp[i][j] = dp[i][j-1] or dp[i-1][j] or dp[i][j-2]

        return dp[-1][-1]
   
if __name__ == '__main__':
    import doctest
    doctest.testmod()

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        """
        Given an input string (s) and a pattern (p),
        implement wildcard pattern matching with support for '?' and '*'.

        '?' Matches any single character.
        '*' Matches any sequence of characters (including the empty sequence).
        The matching should cover the entire input string (not partial).
        :param s:
        :param p:
        :return:
        >>> solution = Solution()
        >>> solution.isMatch('aa', 'a')
        False
        >>> solution.isMatch('aa', '*')
        True
        >>> solution.isMatch('cb', '?a')
        False
        >>> solution.isMatch('adceb', '*a*b')
        True
        >>> solution.isMatch('acdcb', 'a*c?b')
        False
        """
        transfer = {}
        state = 0

        for c in p:
            if c == '*':
                transfer[state, c] = state
            else:
                transfer[state, c] = state + 1
                state += 1

        accept = state
        state = set([0])
        for c in s:
            state = set([transfer.get((at, token)) for at in state
                         for token in [c, '*', '?']])

        return accept in state

class Solution:
    def longestPalindrome(self, s: str) -> int:
        """
        Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.

        This is case sensitive, for example "Aa" is not considered a palindrome here.

        Note:
        Assume the length of given string will not exceed 1,010.
        :param s:
        :return:

        >>> solution = Solution()
        >>> solution.longestPalindrome('abccccdd')
        7
        >>> solution.longestPalindrome('civilwartestingwhetherthatnaptionoranynartionsoconceivedandsontofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth')
        115
        """
        d = {}
        for c in s:
            d[c] = d.setdefault(c, 0) + 1

        max_odd = 0
        longest_num = 0
        for v in d.values():
            if v % 2 == 0:
                longest_num += v
            else:
                longest_num += v - 1
                max_odd = 1

        return longest_num + max_odd
    

class Solution:
    def longestPalindrome(self, s: str) -> str:
        """
        Given a string s, find the longest palindromic substring in s.
        You may assume that the maximum length of s is 1000.

        :param s:
        :return:

        >>> solution = Solution()
        >>> solution.longestPalindrome('babad')
        'bab'
        >>> solution.longestPalindrome('cbbd')
        'bb'
        """
        max_s = ''
        t = '#'+'#'.join(s)+'#'
        for i, c in enumerate(t):
            low, high = i, i
            while 0 <= low-1 and high + 1 < len(t) and t[low-1] == t[high+1]:
                low = low - 1
                high = high + 1

            if len(t[low:high+1]) > len(max_s):
                max_s = t[low:high+1]

        return ''.join(max_s.split('#'))

class Solution:
    def longestPalindromeV02(self, s: str) -> str:
        length = len(s)
        max_s = ''
        dp = [[True for _ in range(length)] for _ in range(length)]
        for i in range(length):
            for j in range(length-i):
                if i + j < length:
                    if i+j == j+1 and s[j] != s[j+i]:
                        dp[j][j+i] = False
                    elif i+j > j+1 and not(dp[j+1][j+i-1] and s[j] == s[j+i]):
                        dp[j][j+i] = False
    
                    if dp[j][j+i] and i+1 > len(max_s):
                        max_s = s[j:j+i+1]
        return max_s

class Solution:
    def longestPalindrome(self, in_s: str) -> str:
        s = '#' + '#'.join(in_s) + '#'
        s_len = len(s)
        r = [0 for _ in range(s_len)]
        pos = 0
        max_right = 0
        max_s = ''
        for i, c in enumerate(s):
            if i < max_right:
                r[i] = min(max_right-i, r[2*pos-i])
            else:
                r[i] = 1
            while i-r[i] >= 0 and r[i]+i < s_len and s[i-r[i]] == s[i+r[i]]:
                r[i] += 1

            if r[i]+i-1 > max_right:
                max_right = r[i]+i-1
                pos = i
            if len(s[i-r[i]+1:i+r[i]]) > len(max_s):
                max_s = s[i-r[i]+1:i+r[i]]

        return ''.join(max_s.split('#'))

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        """
        The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

        P   A   H   N
        A P L S I I G
        Y   I   R
        And then read line by line: "PAHNAPLSIIGYIR"

        Write the code that will take a string and make this conversion given a number of rows:

        string convert(string s, int numRows);

        :param s:
        :param numRows:
        :return:

        >>> solution = Solution()
        >>> solution.convert('PAYPALISHIRING', 3)
        'PAHNAPLSIIGYIR'
        >>> solution.convert('PAYPALISHIRING', 4)
        'PINALSIGYAHRPI'
        >>> solution.convert('', 1)
        ''
        >>> solution.convert('A', 1)
        'A'
        """
        if numRows == 1 or numRows >= len(s):
            return s

        L = [''] * numRows
        index, step = 0, 1

        for x in s:
            L[index] += x
            if index == 0:
                step = 1
            elif index == numRows - 1:
                step = -1
            index += step

        return ''.join(L)

class Solution:
    def lengthOfLastWord(self, s: str) -> int:
        res = s.split()
        if not res:
            return 0
        return len(res[-1])

class Solution:
    def isPalindrome(self, s: str) -> bool:
        """
        Determine whether an integer is a palindrome.
        An integer is a palindrome when it reads the same backward as forward.
        :param s:
        :return:
        >>> solution = Solution()
        >>> solution.isPalindrome('A man, a plan, a canal: Panama')
        True
        >>> solution.isPalindrome('race a car')
        False
        """
        r = ''.join(e for e in s if e.isalnum()).lower()
        return r == r[::-1]


if __name__ == '__main__':
    import doctest
    doctest.testmod()

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        """
        Given two strings s and t, determine if they are isomorphic.

        Two strings are isomorphic if the characters in s can be replaced to get t.

        All occurrences of a character must be replaced with another character
        while preserving the order of characters. No two characters may map to
        the same character but a character may map to itself.

        :param s:
        :param t:
        :return:
        >>> solution = Solution()
        >>> solution.isIsomorphic('egg', 'add')
        True
        >>> solution.isIsomorphic('foo', 'bar')
        False
        >>> solution.isIsomorphic('paper', 'title')
        True
        """
        return len(set(zip(s, t))) == len(set(s)) == len(set(t))

class Solution:
    def countSubstrings(self, s: str) -> int:
        """
        Given a string, your task is to count how many palindromic substrings in this string.

        The substrings with different start indexes or end indexes are counted as different
        substrings even they consist of same characters.

        :param s:
        :return:
        >>> solution = Solution()
        >>> solution.countSubstrings('abc')
        3
        >>> solution.countSubstrings('aaa')
        6
        """
        length = len(s)
        dp = [[False for _ in range(length)] for _ in range(length)]
        cnt = 0
        for i in range(0, length):
            for j in range(length-i):
                if j == j+i:
                    dp[j][j+i] = True
                    cnt += 1
                elif j+i == j+1 and s[j] == s[j+i]:
                    dp[j][j+i] = True
                    cnt += 1
                elif j+1 <= length and j+i-1 >= 0 and s[j] == s[j+i]:
                    dp[j][j+i] = dp[j+1][j+i-1]
                    if dp[j][j+i]:
                        cnt += 1
        return cnt

class Solution:
    def countBinarySubstrings(self, s: str) -> int:
        """
        Give a string s, count the number of non-empty (contiguous) substrings
        that have the same number of 0's and 1's, and all the 0's and all the 1's
        in these substrings are grouped consecutively.

        Substrings that occur multiple times are counted the number of times they occur.

        :param s:
        :return:
        >>> solution = Solution()
        >>> solution.countBinarySubstrings('00110011')
        6
        >>> solution.countBinarySubstrings('10101')
        4
        >>> solution.countBinarySubstrings('00110')
        3
        """
        s = list(map(len, s.replace('01', '0 1').replace('10', '1 0').split()))
        return sum(min(a, b) for a, b in zip(s, s[1:]))

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for n in nums:
            res ^=n
        return res
    
    def singleNumber(self, nums: List[int]) -> int:
        from functools import reduce
        return reduce(operator.xor, nums)

class Solution:
    def reverseBits(self, n: int) -> int:
        return int(bin(n)[2:].zfill(32)[::-1], 2)

    def reverseBits01(self, n: int) -> int:
        for i in range(16):
            if (n>>i & 1) != (n >> (31-i) & 1):
                n ^= ((1<<i) | (1<<(31-i)))
        return n
        
    def reverseBits02(self, n: int) -> int:
        return int("{:032b}".format(n)[::-1], 2)

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        res = 0
        while n != 0:
            n &= n-1
            res += 1
        return res

class Solution:
    def isPowerOfFour(self, num: int) -> bool:
        return num >0 and num&(num-1)==0 and len(bin(num)[3:])%2 == 0

class Solution:
    def getSum(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF
        MAX = 0x7FFFFFFF
        while b != 0:
            a, b = (a ^ b) & MASK, ((a & b) << 1) & MASK
        return a if a <= MAX else ~(a^MASK)

class Solution:
    def toHex(self, num: int) -> str:
        if num == 0:
            return '0'
        res = ''
        for i in range(8):
            res = '0123456789abcdef'[num&15] + res
            num >>= 4
        return res.lstrip('0')

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        nums_len = len(nums)
        max_num = 2**nums_len
        res = list()
        for i in range(max_num):
            b = '0'*(nums_len-len(bin(i)[2:])) + bin(i)[2:]
            t = list()
            for j, v in enumerate(b):
                if v == '1':
                    t.append(nums[j])
            res.append(t)
        return res

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ones, twos, threes = 0, 0, 0
        for num in nums:
            twos |= ones & num
            ones ^= num
            threes = ones & twos
            ones &= ~threes
            twos &= ~threes
            
        return ones

class Solution:
    def findRepeatedDnaSequences(self, s: str) -> List[str]:
        res = set()
        keys = set()
        for i in range(len(s)-9):
            if s[i:i+10] in keys:
                res.add(s[i:i+10])
            else:
                keys.add(s[i:i+10])
        return list(res)

class Solution:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        while m < n:
            n &= n-1
        return n

class Solution:
    def singleNumber(self, nums: List[int]) -> List[int]:
        from functools import reduce
        import operator
        xor = reduce(operator.xor, nums)

        xor = xor & (-xor) 
        a, b = 0, 0
        for num in nums:
            if num & xor:
                a ^= num
            else:
                b ^= num
        return [a, b]

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        d = {sum(1<<(ord(c)-ord('a')) for c in set(w)):len(w) for w in sorted(words, key=len)}
        return max([d[i]*d[j] for i in d for j in d if not i&j] or [0])

class Solution:
    def countBits(self, num: int) -> List[int]:
        res = [0]
        while len(res) < num + 1:
            res += [x+1 for x in res]
        return res[:num+1]

class Solution:
    def validUtf8(self, data: List[int]) -> bool:
        count = 0
        for i in data:
            if count == 0:
                if (i>>3) == 0b11110:
                    count = 3
                elif (i>>4) == 0b1110:
                    count = 2
                elif (i>>5) == 0b110:
                    count = 1
                elif (i>>7) != 0:
                    return False
            else:
                if (i>>6) != 0b10:
                    return False
                count -= 1
        return count == 0

class Solution:
    def integerReplacement(self, n: int) -> int:
        cnt = 0
        while n != 1:
            if n & 1:
                if ((n >>1) & 1) and n != 3:
                    n = n+1
                else:
                    n = n-1
            else:
                n >>= 1
            cnt += 1
        return cnt

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        ans = 0
        for i in range(32)[::-1]:
            ans <<= 1
            prefixes = { num >> i for num in nums}
            ans += any(ans ^ 1 ^ p in prefixes for p in prefixes)
        return ans

class Solution:
    def totalHammingDistance(self, nums: List[int]) -> int:
        return sum([b.count('0')*b.count('1') for b in zip(*map("{:032b}".format, nums))])

class Solution:
    def subarrayBitwiseORs(self, A: List[int]) -> int:
        ans = set()
        cur = {0}
        for x in A:
            cur = {y|x for y in cur} | {x}
            ans |= cur
        return len(ans)

class Solution:
    def maxAbsValExpr(self, arr1: List[int], arr2: List[int]) -> int:
        A, B, C, D= [], [], [], []
        for i in range(len(arr1)):
            x, y = arr1[i], arr2[i]
            A.append(x + y + i)
            B.append(x + y - i)
            C.append(x - y + i)
            D.append(x - y - i)
            
        a = max(A) - min(A)
        b = max(B) - min(B)
        c = max(C) - min(C)
        d = max(D) - min(D)        
        return max(a, b, c, d)

class Solution:
    def maxLength(self, arr: List[str]) -> int:
        dp = [set()]
        for a in arr:
            if len(set(a)) < len(a): continue
            a = set(a)
            for c in dp:
                if a&c: continue
                dp.append(a|c)
        return max(len(a) for a in dp)

class Solution:
    def smallestSufficientTeam(self, req_skills: List[str], people: List[List[str]]) -> List[int]:
        n, m = len(req_skills), len(people)
        key = {v:i for i, v in enumerate(req_skills)}
        dp = {0:[]}
        
        for i, p in enumerate(people):
            skill = 0
            for k in p:
                if k in key:
                    skill |= 1 << key[k]
            if skill == 0: continue
            
            if skill in dp and len(dp[skill]) == 1: continue
            
            for k, need in list(dp.items()):
                with_him = skill | k
                if with_him == k: continue
                if with_him not in dp or len(dp[with_him]) > len(need) + 1:
                    dp[with_him] = need + [i]
        
        return dp[(1 << n) - 1]
                

class Solution:
    # [1] 开始
    def getMask(self, word):
        mask = 0
        for c in word:
            mask |= 1 << (ord(c) - ord('a'))
        return mask
    # [1] 结束

    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        # [2] 开始
        words = [self.getMask(w) for w in words]
        d = {}
        for w in words:
            d[w] = d.get(w, 0) + 1
        # [2] 结束

        ans = []
        for p in puzzles:
            mask = self.getMask(p)
            sub_mask = mask
            head_mask = 1 << (ord(p[0]) - ord('a'))
            cnt = 0
            # [3] 开始
            while sub_mask:
                # [4] 开始
                if sub_mask & head_mask:
                    cnt += d.get(sub_mask, 0)
                # [4] 结束
                sub_mask = (sub_mask-1)&mask
            # [3] 结束
            ans.append(cnt)
        return ans

class Solution:
    def maxScoreWords(self, words: List[str], letters: List[str], score: List[int]) -> int:
        from collections import Counter
        words_score = [sum(score[ord(c)-ord('a')] for c in word) for word in words]
        words_counter = [Counter(word) for word in words]
        self.max_score = 0

        def dfs(start, current_score, letter_counter):
            if current_score+sum(words_score[start:]) <= self.max_score:
                return
            self.max_score = max(self.max_score, current_score)

            for i, w_cnt in enumerate(words_counter[start:], start):
                if all(n <= letter_counter.get(c, 0) for c, n in w_cnt.items()):
                    dfs(i+1, current_score+words_score[i], {c:n-w_cnt.get(c, 0) for c, n in letter_counter.items()})
        
        dfs(0, 0, Counter(letters))
        return self.max_score

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and not n & (n-1)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        return sum(range(len(nums)+1)) - sum(nums)

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        from functools import reduce
        return chr(reduce(int.__xor__, map(ord, s+t)))

class Solution:
    def readBinaryWatch(self, num: int) -> List[str]:
        return [f"{h}:{m:02d}" for h in range(12) for m in range(60) if (bin(h)+bin(m)).count('1') == num]