from typing import List, Optional

# given array of continuous numbers differing by 1, find missing numbers in the sequence
# t.c. O(n+(max(nums)−min(nums))), space O((max(nums)−min(nums))) - t.c. can be huge, consider intervals
# [1, 2, 4, 5, 7] - 3, 6 are missing
from typing import List
def find_missing(nums: List) -> List:
    # edge cases
    if not (hasattr(nums, "__getitem__") and hasattr(nums, "__len__")):    # if we use Iterable instead of List
        raise TypeError("Must be a sequence with indexing.")               # needed to avoid Iterator - no len()
    if not isinstance(nums, Iterable):
        raise TypeError('Check type')
    if not all(isinstance(x, int) for x in nums):
        raise TypeError("All elements must be integers")
        
    if len(nums) < 2:
        return []
    # initiate vars
    m = []
    # iterate
    for idx in range(len(nums)-1):
        if nums[idx+1] - nums[idx] > 1:
            m.extend(list(range(nums[idx]+1, nums[idx+1])))
    return m    


nums = [1, 2, 4, 5, 7]
find_missing(nums)

# longest_increasing_subsequence in a list
def longest_increasing(nums: List) -> int:
    # edge cases
    if not (hasattr(nums, "__getitem__") and hasattr(nums, "__len__")):    # if we use Iterable instead of List
        raise TypeError("Must be a sequence with indexing.")
    
    if not all(isinstance(x, (int, float)) for x in nums):
        raise TypeError("All elements must be numeric.")
        
    if not isinstance(nums, list): raise TypeError('m')
    if not nums:
        return 0
    elif len(nums) == 1:
        return 1
        
    # initiate
    max_len, cur_len = 1, 1
    # iterate
    for i in range(len(nums)-1):
        if nums[i+1] > nums[i]:
            cur_len += 1
            max_len = max(max_len, cur_len)
        else:
            cur_len = 1
    return max_len
        
    
nums = [1, 2, 4, 3, 5, 7, 9, 3, 2, 1, 2]
longest_increasing(nums)

from typing import List
def zero_out(matrix: List[List[int]]) -> List[List[int]]:
    """
    Zeroes out all rows and columns of a 2D matrix where there is a zero.
    Args:
    matrix: A 2D matrix.
    Returns:
    A new 2D matrix with all rows and columns that contain a zero zeroed out.
    """
    # edge cases
    
    # 1. Validate that matrix is not empty and truly a list of lists
    if not matrix:
        return []
    if not isinstance(matrix, list) or any(not isinstance(row, list) for row in matrix):
        raise TypeError('Matrix must be a non-empty list of lists.')

    # (Optional) Check all elements are integers:
    if any(any(not isinstance(x, int) for x in row) for row in matrix):
        raise TypeError("All elements must be integers.")

    # 2. Make a copy if you really want a "new" matrix
    new_matrix = [row[:] for row in matrix]
        
    # initiate
    zero_rows = set()
    zero_cols = set()
        
    # iterate
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if j in zero_cols: continue
            if matrix[i][j]==0:
                zero_rows.add(i)
                zero_cols.add(j)
                
    for i in zero_rows:
        matrix[i] = [0]*len(matrix[0])
    for j in zero_cols:
        for i in range(len(matrix)):
            matrix[i][j]=0
            
    return matrix


matrix = [
  [1, 2, 3],
  [4, 5, 0],
  [6, 7, 8]
]
zero_out(matrix)

# time = O(n^2) because we iterate n centers O(n), expanding each left and right O(n)
# space = O(1)
def longest_ps(s: str) -> str:
    if not isinstance(s, str):
        raise ValueError("Input must be a string.")
    if len(s) < 2:
        return s

    def expand_center(left: int, right: int) -> tuple:        
        while left >= 0 and right < len(s) and s[left] == s[right]: # expand until palindrome
            left -= 1
            right += 1        
        return left + 1, right - 1        # return bounds of palindrome

    start, end = 0, 0                     # start and end of longest palindrome
    for i in range(len(s)):
        # Check for odd-length palindromes (single character center)
        left1, right1 = expand_center(i, i)
        # Check for even-length palindromes (two character center)
        left2, right2 = expand_center(i, i + 1)

        # Update the longest palindrome found
        if right1 - left1 > end - start:
            start, end = left1, right1
        if right2 - left2 > end - start:
            start, end = left2, right2

    return s[start:end + 1]

# time = O(logN), space = O(1)
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        
        lower_bound = self.findBound(nums, target, True)
        if (lower_bound == -1):
            return [-1, -1]
        
        upper_bound = self.findBound(nums, target, False)
        
        return [lower_bound, upper_bound]
        
    def findBound(self, nums: List[int], target: int, isFirst: bool) -> int:
        
        N = len(nums)
        begin, end = 0, N - 1
        while begin <= end:
            mid = int((begin + end) / 2)    
            
            if nums[mid] == target:
                
                if isFirst:
                    # we found our lower bound
                    if mid == begin or nums[mid - 1] < target:
                        return mid
                    # search on left side for bound
                    end = mid - 1
                else:                    
                    # we found our upper bound.
                    if mid == end or nums[mid + 1] > target:
                        return mid
                    # search on right side for bound
                    begin = mid + 1
            
            elif nums[mid] > target:
                end = mid - 1
            else:
                begin = mid + 1
        
        return -1

# time = O(nlogn), space = O(n)
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        intervals.sort(key=lambda x: x[0])

        merged = []
        for interval in intervals:
            # if the list of merged intervals is empty or if the current
            # interval does not overlap with the previous, simply append it.
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
            # otherwise, there is overlap, so we merge the current and previous
            # intervals.
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

# time = space = O(n)
# Depth First Search (DFS)
class TreeNode(object):
    """ Definition of a binary tree node."""
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        
        
# Serialization 
class Codec:

    def serialize(self, root):
        """ Encodes a tree to a single string.
        :type root: TreeNode
        :rtype: str
        """
        def rserialize(root, string):
            """ a recursive helper function for the serialize() function."""
            # check base case
            if root is None:
                string += 'None,'
            else:
                string += str(root.val) + ','
                string = rserialize(root.left, string)
                string = rserialize(root.right, string)
            return string
        
        return rserialize(root, '')
    
    
# Deserialization 
class Codec:

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        def rdeserialize(data_list):
            """ a recursive helper function for deserialization."""
            if data_list[0] == 'None':
                data_list.pop(0)
                return None
                
            root = TreeNode(data_list[0])
            data_list.pop(0)
            root.left = rdeserialize(data_list)
            root.right = rdeserialize(data_list)
            return root

        data_list = data.split(',')
        root = rdeserialize(data_list)
        return root

# time = N⋅5^(N/2+1), space = N⋅5^(N/2). Iterative approach (level order traversal) has the same complexity 
def findStrobogrammatic(n: int) -> List[str]:
    reversible_pairs = [
        ['0', '0'], ['1', '1'], 
        ['6', '9'], ['8', '8'], ['9', '6']
    ]

    def generate_strobo_numbers(n, final_length):
        if n == 0:
            # 0-digit strobogrammatic number is an empty string.
            return [""]

        if n == 1:
            # 1-digit strobogrammatic numbers.
            return ["0", "1", "8"]

        prev_strobo_nums = generate_strobo_numbers(n - 2, final_length)
        curr_strobo_nums = []

        for prev_strobo_num in prev_strobo_nums:
            for pair in reversible_pairs:
                if pair[0] != '0' or n != final_length:
                    curr_strobo_nums.append(pair[0] + prev_strobo_num + pair[1])

        return curr_strobo_nums

    return generate_strobo_numbers(n, n)

findStrobogrammatic(2)

# time = O(N * (4^N)), where N = len of digits, space = O(n)
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        # If the input is empty, immediately return an empty answer array
        if len(digits) == 0: 
            return []
        
        # Map all the digits to their corresponding letters
        letters = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl", 
                   "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}
        
        def backtrack(index, path):
            # If the path is the same length as digits, we have a complete combination
            if len(path) == len(digits):
                combinations.append("".join(path))
                return
            
            # Get the letters that the current digit maps to, and loop through them
            possible_letters = letters[digits[index]]
            for letter in possible_letters:
                # Add the letter to our current path
                path.append(letter)
                # Move on to the next digit
                backtrack(index + 1, path)
                # Backtrack by removing the letter before moving onto the next
                path.pop()

        # Initiate backtracking with an empty path and starting index of 0
        combinations = []
        backtrack(0, [])
        return combinations

# from comments
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        lookup = {
            "2": ["a", "b", "c"],
            "3": ["d", "e", "f"],
            "4": ["g", "h", "i"],
            "5": ["j", "k", "l"],
            "6": ["m", "n", "o"],
            "7": ["p", "q", "r", "s"],
            "8": ["t", "u", "v"],
            "9": ["w", "x", "y", "z"]
        }
        
        letter_lists = []
        for ch in digits:
            letter_lists.append(lookup[ch])
            
        while len(letter_lists) > 1:
            l1 = letter_lists.pop()
            l2 = letter_lists.pop()
            combos = []
            for i in l1:
                for j in l2:
                    combos.append(j + i)
            letter_lists.append(combos)
            
        return [] if not letter_lists else letter_lists[0]

class LRUCache(object):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

from collections import OrderedDict
class LRUCache(OrderedDict):

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.capacity = capacity

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        if key not in self:
            return - 1
        
        self.move_to_end(key)
        return self[key]

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last = False)

# time = O(1), space = O(capacity)
class DLinkedNode(): 
    def __init__(self):
        self.key = 0
        self.value = 0
        self.prev = None
        self.next = None
            
class LRUCache():
    def _add_node(self, node):
        """
        Always add the new node right after head.
        """
        node.prev = self.head
        node.next = self.head.next

        self.head.next.prev = node
        self.head.next = node

    def _remove_node(self, node):
        """
        Remove an existing node from the linked list.
        """
        prev = node.prev
        new = node.next

        prev.next = new
        new.prev = prev

    def _move_to_head(self, node):
        """
        Move certain node in between to the head.
        """
        self._remove_node(node)
        self._add_node(node)

    def _pop_tail(self):
        """
        Pop the current tail.
        """
        res = self.tail.prev
        self._remove_node(res)
        return res

    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.cache = {}
        self.size = 0
        self.capacity = capacity
        self.head, self.tail = DLinkedNode(), DLinkedNode()

        self.head.next = self.tail
        self.tail.prev = self.head
        

    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        node = self.cache.get(key, None)
        if not node:
            return -1

        # move the accessed node to the head;
        self._move_to_head(node)

        return node.value

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: void
        """
        node = self.cache.get(key)

        if not node: 
            newNode = DLinkedNode()
            newNode.key = key
            newNode.value = value

            self.cache[key] = newNode
            self._add_node(newNode)

            self.size += 1

            if self.size > self.capacity:
                # pop the tail
                tail = self._pop_tail()
                del self.cache[tail.key]
                self.size -= 1
        else:
            # update the value.
            node.value = value
            self._move_to_head(node)

def lengthOfLongestSubstring(s: str) -> int:
    ''' My Solution (Accepted)
        Iterate over each char in string with some logic    
    '''    
    
    curr, max_ = '', ''
    for idx, c in enumerate(s):
        if not curr:                             # add current char if curr is empty
            curr = c                        
        elif curr and c not in curr:             # add current char if it's not in curr
            curr += c
        elif curr and curr[-1] == c:             # reset curr if current char is also the last one in curr
            curr = c
        else:                                    # current char in curr, but not the last one - find its index in s,
            temp_idx = idx - 1                   # but not in curr(!) because curr may be shorter. Make curr include 
            while s[temp_idx] != c:              # everyting after (because there is no c) + c at current idx
                temp_idx -= 1
            curr = s[temp_idx+1 : idx+1]

        max_ = max(curr, max_, key=len)
                
    return len(max_)


def lengthOfLongestSubstring2(s: str) -> int:
    '''LeetCode solution beautified by me
       We use HashSet to store the characters in current window [i,j) (j = i initially).
       Then we slide the index j to the right. If it is not in the HashSet, we slide j further.
       Doing so until s[j] is already in the HashSet. At this point, we found the maximum size
       of substrings without duplicate characters start with index i.
       If we do this for all i, we get our answer
    '''
    mapp = {c:0 for c in s}
    left = 0
    max_len = 0
    for right, c in enumerate(s):
        mapp[c] += 1
        while mapp[c] > 1:
            mapp[ s[left] ] -= 1
            left += 1
        max_len = max(max_len, right - left + 1)

    return max_len

    
s1 = 'abcbacbb'
s2 = 'bbbbb'
s3 = 'pwwkew'
s4 = ''

# 3,1,3,0
for s in [s1, s2, s3, s4]:
    print( lengthOfLongestSubstring(s), end=', ' )
    
print()    
for s in [s1, s2, s3, s4]:
    print( lengthOfLongestSubstring2(s), end=', ' )

def lengthOfLongestSubstring(s: str) -> int:
    '''
        Another my solution
        Time c.  = O(3n) = O(n)
        Space c. = O(2n) = O(n)?
    '''
    def all_unique(s2: str) -> bool:
        stack = []
        for c in s2:
            if c not in stack:
                stack.append(c)
        return len(s2) == len(stack)
    
    i,j = 0,1
    max_len = 0
    length = len(s)
    while i < length and j < length:
        curr_str = s[i:j]
        if all_unique(curr_str):
            curr_len = len(curr_str)
            if curr_len > max_len:
                max_len = curr_len
            j += 1
        else:
            while i < j and not all_unique(s[i:j]):
                i += 1
    return max_len
        
    
    
def lengthOfLongestSubstring2(s: str) -> int:
    '''
        Brute force
        Time c.  = O((n^2)/2) = O(n^2)
        Space c. = O(n) because of curr_str? Or O(1)?
    '''
    max_len = 0
    for i in range(len(s)):
        for j in range(i+1, len(s)):
            curr_str = s[i:j]
            if len(curr_str) == len(set(curr_str)):
                curr_len = len(curr_str)
                if curr_len > max_len:
                    max_len = curr_len
    return max_len


s1 = 'abcbacbb'
s2 = 'bbbbb'
s3 = 'pwwkew'
s4 = ''

# 3,1,3,0
for s in [s1, s2, s3, s4]:
    print( lengthOfLongestSubstring(s), end=', ' )
    
print()    
for s in [s1, s2, s3, s4]:
    print( lengthOfLongestSubstring2(s), end=', ' )

# LeetCode provides no solution for this
import string

def myAtoi(s: str) -> int:
    '''
        My accepted solution.
        LeetCode doesn't provide a solution
    '''    
    s = s.strip()
    signs = '-+'
    if s[0] in signs:
        sign = s[0]
        s = s[1:]
    else:
        sign = '+'
        
    nums = []            
    for idx, c in enumerate(s):        
        if c in string.digits:
            nums.append(c)            
        else:            
            break
           
    if not nums:
        return 0
    
    res = 0    
    for idx, num in enumerate(nums):
        power = len(nums) - (idx + 1)
        res += int(num)*10**power
        
    if sign == '-':
        res = -res
        
    if res < -2**31:
        res = -2**31
    elif res > 2**31 - 1:
        res = 2**31 - 1
        
    return res


n1 = '42'
n2 = '-42'
n3 = '4193 with words'
n4 = 'words and 987'
n5 = '-91283472332'

for num in [n1, n2, n3, n4, n5]:
    print(myAtoi(num))

def romanToInt(s: str) -> int:
    
    s   = s.strip()
        
    conv = {
                'I': 1,
                'V': 5,
                'X': 10,
                'L': 50,
                'C': 100,
                'D': 500,
                'M': 1000,
                'IV': 4,
                'IX': 9,
                'XL': 40,
                'XC': 90,
                'CD': 400,
                'CM': 900,
            }
    
    res = 0
    i = 0
    while i < len(s)-1:
        if s[i:i+2] in conv:
            res += conv[ s[i:i+2] ]
            i += 2
        else:
            res += conv[ s[i] ]
            i += 1
    if i == len(s)-1:
        res += conv[s[i]]
        
    return res


def romanToInt2(s: str) -> int:
    '''
        Leetcode solution - runs a bit faster
    '''
    
    values = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000,
        }
    
    total = 0
    i = 0
    while i < len(s):        
        if i+1 < len(s) and values[ s[i] ] < values[ s[i+1] ]:                   # subtractive case ('IX')
            total += values[ s[i+1] ] - values[ s[i] ]
            i += 2
        else:
            total += values[s[i]]
            i += 1
                        
    return total

    
s1 = 'III'
s2 = 'IV'
s3 = 'IX'
s4 = 'LVII'
s5 = 'MCMXCIV'

for s in [s1, s2, s3, s4, s5]:
    print( romanToInt(s) )
    
for s in [s1, s2, s3, s4, s5]:
    print( romanToInt2(s) )

def threeSum(nums: List[int]) -> List[List[int]]:
    '''
        My accepted solution
        Your runtime beats 93.44% of python3 submissions
        Your memory usage beats 98.69 % of python3 submissions
    '''
    
    n = len(nums)
    nums.sort()        
    res = set()                                               # helps avoid duplicates and decrease scpace complexity

    for i in range( n-1 ):

        if nums[i] > 0 or (i > 0 and nums[i] == nums[i-1]):    # next vals cannot sum to 0 in sorted arr if num[i] > 0
            continue                                          # it's a duplicate if nums[i] == nums[i-1]
                                                              # helps greatly decrease run time (per LeetCode metrics)
        l = i+1
        r = n-1

        while l < r:
            sum_ = nums[i] + nums[l] + nums[r]
            if sum_ < 0:
                l += 1
            elif sum_ > 0:
                r -= 1
            else:             
                res.add( (nums[i], nums[l], nums[r]) )
                l += 1
                r -= 1

    return list(res)


a1 = [-1, 0, 1, 2, -1, -4]
a2 = []
a3 = [0]

for a in [a1, a2, a3]:
    print( threeSum(a) )

def removeDuplicates(nums: List[int]) -> int:
    '''
        My accepted solution - moves arr elems, but doesn't modify them
                
        Your runtime beats 46.14 % of python3 submissions
        Your memory usage beats 45.38 % of python3 submissions
    '''    
    if not nums:
        return 0
    elif len(set(nums)) == 1:                                     # covers cases like [1,1], [1,1,1], etc.
        return 1

    i = 0
    j = 1
    while j < len(nums) and i < len(nums):

        if i == j:
            j += 1
        
        if nums[j] == nums[i]:                                    # j moves faster, skipping duplicates
            j += 1        
        elif nums[j] > nums[i]:                                      
            nums[i+1], nums[j] = nums[j], nums[i+1]               # if found greater elem than i, swap with i+1
            j += 1
            i += 1
                        
    return i + 1


def removeDuplicates2(nums: List[int]) -> int:
    '''
        LeetCode solution (translated into Python) - modifies arr by overwriting its elems in the first half
        with the correct elems moved from the second half
                
        Your runtime beats 51.32 % of python3 submissions
        Your memory usage beats 45.38 % of python3 submissions.
    '''
    if not nums:
        return 0
    k = 0
    for i in range(1, len(nums)):
        if nums[i] != nums[k]:
            k += 1
            nums[k] = nums[i]
            

    return k + 1

    
print('My solution')
nums = [1,1,2]
print( removeDuplicates(nums) )
print( nums )

nums = [0,0,1,1,1,2,2,3,3,4]
print( removeDuplicates(nums) )
print( nums )

print('LeetCode solution')
nums = [1,1,2]
print( removeDuplicates2(nums) )
print( nums )

nums = [0,0,1,1,1,2,2,3,3,4]
print( removeDuplicates2(nums) )
print( nums )

def sortedSquares(nums: List[int]) -> List[int]:
    '''
        LeetCode solution    
    '''    
    n = len(nums)
    result = [0] * n
    left = 0
    right = n - 1
    for i in range(n - 1, -1, -1):
        if abs(nums[left]) < abs(nums[right]):
            square = nums[right]
            right -= 1
        else:
            square = nums[left]
            left += 1
        result[i] = square * square
                
    return result

import math

def multiply(num1: str, num2: str) -> str:
    '''
        My accepted solution
        Your runtime beats 72.41 % of python3 submissions
        Too much memory
        
        Another solution - dict = {'0':0, '1':1, etc.} help avoid ord() and chr()
    '''
    
    if num1=='0' or num2=='0': return '0'
    
    num1 = [ord(c)-ord('0') for c in num1]                                # convert to list of digits
    num1 = sum([e*(10**(len(num1)-idx-1)) for idx,e in enumerate(num1)])  # convert to number
    
    num2 = [ord(c)-ord('0') for c in num2]    
    num2 = sum([e*(10**(len(num2)-idx-1)) for idx,e in enumerate(num2)])
    
    product   = num1*num2
    order     = math.floor(math.log10(product))                           # to avoid math - keep doing n//10 and n%10
    res       = []                                                        # until n//10 is 0
    remainder = product
    for i in range(order,-1,-1):
        res.append(remainder//10**i)
        remainder = remainder%10**i
    
    return ''.join([chr(n+48) for n in res])


def multiply2(num1: str, num2: str) -> str:
    '''
        Shorthand solution from Leetcode discussions - replace str(int) with my conversion to str without str()
        Your runtime beats 20.37 % of python3 submissions
        Your memory usage beats 55.03 % of python3 submissions
    '''
    res = 0
    for i, c1 in enumerate(num1[::-1]):
        for j, c2 in enumerate(num2[::-1]):
            res += (ord(c1)-ord('0')) * (ord(c2)-ord('0')) * (10**(i+j))
    return str(res)
    
    
num1 = '123'
num2 = '456'
multiply2(num1, num2)

# best solution from Leetcode
def multiply(num1: str, num2: str) -> str:
    '''
    N and M - # digits in num1 and num2.
    Time c.: O(M⋅N) - N operations for each of M digits of the second number
    Space c.: O(M+N) - space to store output not included, but strings are immutable =>
    a temp data structure, using O(M+N) space, is required to store the answer while it is updated.    
    '''
    if num1 == "0" or num2 == "0":
        return "0"

    # Initialize answer as a string of zeros of length N.
    N = len(num1) + len(num2)
    answer = [0] * N

    # Reverse num1 and num2
    first_number = num1[::-1]
    second_number = num2[::-1]

    for place2, digit2 in enumerate(second_number):
        # For each digit in second_number multiply the digit by all digits in first_number.
        for place1, digit1 in enumerate(first_number):
            # The number of zeros from multiplying to digits depends on the place
            # of digit2 in second_number and the place of the digit1 in first_number.
            num_zeros = place1 + place2

            # The digit currently at position numZeros in the answer string
            # is carried over and summed with the current result.
            carry = answer[num_zeros]
            multiplication = int(digit1) * int(digit2) + carry

            # Set the ones place of the multiplication result.
            answer[num_zeros] = multiplication % 10

            # Carry the tens place of the multiplication result by 
            # adding it to the next position in the answer array.
            answer[num_zeros + 1] += multiplication // 10

    # Pop the excess 0 from the end of answer.
    if answer[-1] == 0:
        answer.pop()

    return ''.join(str(digit) for digit in reversed(answer))

# more concise Leetcode solution
def multiply(num1, num2):
        """
        :type num1: str
        :type num2: str
        :rtype: str
        """
        if num1=='0' or num2=='0':
            return '0'
        n = len(num1) + len(num2)
        answer = [0]*n
        num11 = num1[::-1]
        num22 = num2[::-1]
        
        for idx2, digit2 in enumerate(num22):
            for idx1, digit1 in enumerate(num11):                
                num_zeros = idx2 + idx1
                carry = answer[ num_zeros ]
                product = int(digit1)*int(digit2) + carry
                answer[ num_zeros ] = product % 10
                answer[ num_zeros+1 ] += product // 10
                
        if answer[-1] == 0:
            answer.pop()
            
        return ''.join(str(d) for d in reversed(answer))

ord('1')-ord('0')

ord('A'), chr(48)

from collections import defaultdict

def groupAnagrams(strs: List[str]) -> List[List[str]]:
    '''
        My accepted solution
        Your runtime beats 45% of python3 submissions
        Your memory usage beats 55% of python3 submissions
        
        Time c.: O(NKlogK), where N = len(strs), K = max_len of s in strs.
        Outer loop = O(N) (iterate over strs), then sort each s in O(KlogK) time
        
        Space c.: O(NK) - content of res
    '''        
    res = defaultdict(list)
    for s in strs:
        res[ ''.join(sorted(s)) ].append(s)

    return res.values()


def groupAnagrams2(strs: List[str]) -> List[List[str]]:
    '''
        Optimized O(NK) time and space c. solution from LeetCode.
        Two str = anagrams iff their char counts are the same ==> transform each str into char count
        consisting of a tuple of 26 non-negative integers, one per letter, which are used as keys in hash map
    '''    
    res = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ ord(c)-ord('a') ] += 1
        res[ tuple(count) ].append(s)

    return res.values()

strs = ["eat","tea","tan","ate","nat","bat"]
groupAnagrams2(strs)

def minWindow(s: str, t: str) -> str:
    '''
    My solution from scratch
    Time c. O(3n) => O(n)?
    Space c. O(n) because of res? 
    '''
    def build_map(string: str) -> str:        
        mapp = {}
        for c in string:
            if c in mapp:
                mapp[c] += 1
            else:
                mapp[c] = 1
        return mapp
    
    def is_map2_in_map1(map1: dict, map2: dict) -> bool:
        for k in map2:
            if k not in map1:
                return False
            if map1[k] < map2[k]:
                return False
        return True
    
    min_len = 10**5
    res     = ''
    map_t = build_map(t)
    l, r = 0, 1
    while l < r and r < len(s)+1:
        if is_map2_in_map1(build_map(s[l:r]), map_t):
            if len(s[l:r]) < min_len:
                min_len = len(s[l:r])
                res = s[l:r]
            l += 1
        else:
            r += 1
    return res    

# my concise solution(based on Leetcode solution). Time/space c. O(n+m)
from collections import Counter

def minWindow(s, t):

    if not t or not s:
        return ''
    dict_t = Counter(t)                     # dict unique chars in t
    len_t  = len(dict_t)                    # count unique chars in t
    dict_curr = {}                          # dict unique chars in curr win
    len_curr  = 0                           # count unique chars in curr window
    l,r = 0,0
    res = float('inf'), None, None          # shortest window length, l, r

    while r < len(s):

        char = s[r]
        dict_curr[ char ] = dict_curr.get(char, 0) + 1
        if char in dict_t and dict_curr[char] == dict_t[char]:
            len_curr += 1

        while l <= r and len_curr == len_t:
            char = s[l]
            if r - l + 1 < res[0]:
                res = (r - l + 1, l, r)

            dict_curr[ char ] -= 1
            if char in dict_t and dict_curr[char] < dict_t[char]:
                len_curr -= 1
            l += 1

        r += 1
    return '' if res[0]==float('inf') else s[ res[1]:res[2]+1 ]

# Leetcode solution
from collections import Counter


def minWindow(s: str, t: str) -> str:
    '''
        LeetCode's solution. Time c. O(m+n)    
    '''    

    if not t or not s:
        return ''
        
    l, r     = 0, 0
    dict_t   = Counter(t)                                     # count of all chars in t    
    required = len(dict_t)                                  # num of unique chars in t that must be in desired window
    
    formed = 0                                       # num unique chars from t in current window in desired frequency
                                                             # e.g. if t=="AABC" => two A's, one B, one C => formed=3
    
    window_counts = {}                                         # count of all unique chars in current window    
    ans = float("inf"), None, None                             # ans = tuple(window length, left, right)

    while r < len(s):

        
        char = s[r]                                                 # add one char from right
        window_counts[ char ] = window_counts.get(char, 0) + 1
        
        if char in dict_t and window_counts[ char ] == dict_t[ char ]:
            formed += 1                               # if current char's frequency == desired count, increment formed
        
        while l <= r and formed == required:                 # contract current window till until it's not 'desirable'
            char = s[l]
            
            if r - l + 1 < ans[0]:                                   # smallest window until now
                ans = (r - l + 1, l, r)

            
            window_counts[char] -= 1                                # char at `left` no longer part of current window
            if char in dict_t and window_counts[ char ] < dict_t[ char ]:
                formed -= 1
            
            l += 1                                                      # contract current window to look for new one
        
        r += 1                                                             # keep expanding once contracting is done
        
    return s[ ans[1]:ans[2]+1 ] if not ans[0]==float("inf") else ''


s = "ADOBECODEBANC"
t = "ABC"
minWindow(s, t)

# Leetcode solution 2
def minWindow(s: str, t: str) -> str:
    """
    Optimized Leetcode solution
    """
    
    if not t or not s:
        return ""

    dict_t = Counter(t)
    required = len(dict_t)

    # Leave only chars from s that occur in t
    filtered_s = []
    for i, char in enumerate(s):
        if char in dict_t:
            filtered_s.append((i, char))

    l, r = 0, 0
    formed = 0
    window_counts = {}

    ans = float("inf"), None, None

    # Same sliding window approach, but on as small list
    while r < len(filtered_s):
        character = filtered_s[r][1]
        window_counts[character] = window_counts.get(character, 0) + 1

        if window_counts[character] == dict_t[character]:
            formed += 1

        while l <= r and formed == required:
            character = filtered_s[l][1]

            end = filtered_s[r][0]
            start = filtered_s[l][0]
            if end - start + 1 < ans[0]:
                ans = (end - start + 1, start, end)

            window_counts[character] -= 1
            if window_counts[character] < dict_t[character]:
                formed -= 1
            l += 1    

        r += 1    
    return s[ ans[1]:ans[2]+1 ] if not ans[0]==float("inf") else ''

samples = [ ("ADOBECODEBANC", "ABC"), ("a", "a"), ("a", "aa") ]
for sample in samples:
    print(minWindow(sample[0], sample[1]))
#Output: "BANC"
#Output: "a"
#Output: ""

def merge(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    """
        My accepted solution
        Your runtime beats 91.85 % of python3 submissions
        Your memory usage beats 85.57 % of python3 submissions
    """
    if not nums2:
        return
    
    new_list = nums1
    i, j = 0, 0
        
    while i<m and j<n:
        if nums2[j] <= new_list[i]:                        
            new_list = new_list[:i] + [nums2[j]] + new_list[i:-1]
            j += 1
            i += 1
            m += 1
        else:
            i += 1
            
    if j < n:
        i = m
        while j < n:
            new_list[i] = nums2[j]
            i += 1
            j += 1
        
    # had to use new_list and this assignment to make it in-place
    nums1[:] = new_list
    
    
def merge2(nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    '''
        Leetcode's solution. Three pointers, moving from the right
        Time c. O(m+n), space c. O(1)
    '''
    p1, p2 = m - 1, n - 1

    # p moves backwards, writing the smallest of p1 or p2.
    for p in range(n + m - 1, -1, -1):
        if p2 < 0:
            break
        if p1 >= 0 and nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
                        
        
nums1 = [1,2,3,0,0,0]
m = 3
nums2 = [2,5,6]
n = 3

merge2(nums1, m, nums2, n)
print('Answer:', nums1)

import string

def isPalindrome(s: str) -> bool:
    '''
        My accepted solution    
    '''    
    if not s:
        return False
    elif len(s) == 1:
        return True
    
    s = ''.join([c for c in s.lower() if c.isalnum()])
    l, r = 0, len(s) - 1
    while l < r:
        if not s[l] == s[r]:
            return False
        l += 1
        r -= 1
        
    return True


def isPalindrome2(s: str) -> bool:
    '''
       Leetcode solution (same approach)
    '''

    i, j = 0, len(s) - 1

    while i < j:
        while i < j and not s[i].isalnum():
            i += 1
        while i < j and not s[j].isalnum():
            j -= 1

        if s[i].lower() != s[j].lower():
            return False

        i += 1
        j -= 1

    return True

s1 = 'A man, a plan, a canal: Panama'
s2 = 'race a car'



isPalindrome(s1)

def isOneEditDistance(s: str, t: str) -> bool:
    '''
         My accepted solution. Time c. O(n), space c. O(n) because s[:-1] will create additional str (str=immutable)
    '''    
    # LENGTH NORMALIZATION
    if len(s) < len(t):
        s,t = t,s
            
    # EDGE CASES
    if (not s and not t) or (abs(len(s) - len(t)) > 1):
        return False
    elif (s[:-1] == t) or (s[1:] == t):
            return True
        
    # SAME LENGTH
    if len(s) == len(t):                
        count = 0
        for i in range(len(s)):
            if s[i] != t[i]:
                count += 1
                #if count > 2: return False
        return True if count == 1 else False
        
    # LENGTH DIFFERENT BY ONE
    elif abs(len(s) - len(t)) == 1:               
        count = 0
        i, j = 0, 0        
        while i < len(s) and j < len(t):
            if s[i] != t[j]:
                count += 1
                if count > 2: return False
                i += 1
            else:
                i += 1
                j += 1                
        return True if count == 1 else False

    
    
def isOneEditDistance2(s: str, t: str) -> bool:
    '''
        Shorter solution from comments (accepted). Time c. O(n), space c. O(1)? 
    '''
    if abs(len(s) - len(t)) > 1 or s == t:
        return False

    found = False
    i = j = 0

    while i < len(s) and j < len(t):
        if s[i] != t[j]:
            if found:
                return False
            found = True
            if len(s) < len(t): i -= 1        # to differentiate from the case of equal lengths
            elif len(s) > len(t): j -= 1

        i += 1
        j += 1

    return True
        
s = 'ab'
t = 'acb'
print( isOneEditDistance(s, t) )

s = ''
t = ''
print( isOneEditDistance(s, t) )

s = 'a'
t = ''
print( isOneEditDistance(s, t) )

s = ''
t = 'A'
print( isOneEditDistance(s, t) )

def productExceptSelf3(nums: List[int]) -> List[int]:
    '''
        My solution; works locally, exceeds time limit when submitted    
    '''
    
    answer = []
    for i in range( len(nums) ):
        product = 1
        for j in range( len(nums) ):
            if j != i:
                product *= nums[j]
        answer.append(product)

    return answer


def productExceptSelf2(nums: List[int]) -> List[int]:
    '''
        Leetcode solution 1. Time c. O(n), space c. O(n) because of two extra arrays   
    '''    
    length = len(nums)    
    L, R, answer = [0]*length, [0]*length, [0]*length
    
    L[0] = 1                                # L[i] - product of all elems to left. L[0] = 1 since nothing to left
    for i in range(1, length):        
        L[i] = nums[i-1] * L[i-1]

    R[-1] = 1                               # R[i] - product of all elems to right. R[-1] = 1 since nothing to right
    for i in reversed(range(length - 1)):        
        R[i] = nums[i + 1] * R[i + 1]
    print(L, R)

    for i in range(length):
        answer[i] = L[i] * R[i]

    return answer


def productExceptSelf(nums: List[int]) -> List[int]:
    '''
        Leetcode solution 2. Time c. O(n), space c. O(1). answer array = array L from solution 1
        and var R contains a running product of elems to right, replacing array R from solution 1
    '''
    length = len(nums)
    answer = [0]*length

    answer[0] = 1                     # answer[i] - product of all elems to left. answer[0] = 1 since nothing to left
    for i in range(1, length):
        answer[i] = nums[i - 1] * answer[i - 1]

    
    R = 1                             # R - running product of elems to right. First R = 1 since nothing to right
    for i in reversed(range(length)):
        answer[i] = answer[i] * R
        R *= nums[i]

    return answer


    
nums = [1,2,3,4]
print( productExceptSelf(nums) )

nums = [-1,1,0,-3,3] 
print( productExceptSelf(nums) )

nums = [1, 5, 7, 2] 
print( productExceptSelf(nums) )

def numberToWords(num: int)-> int:
    '''
        Leetcode solution
    '''
    def ones(num):
        switcher = {
            1: 'One',
            2: 'Two',
            3: 'Three',
            4: 'Four',
            5: 'Five',
            6: 'Six',
            7: 'Seven',
            8: 'Eight',
            9: 'Nine'
        }
        return switcher.get(num)

    def teens(num):
        switcher = {
            10: 'Ten',
            11: 'Eleven',
            12: 'Twelve',
            13: 'Thirteen',
            14: 'Fourteen',
            15: 'Fifteen',
            16: 'Sixteen',
            17: 'Seventeen',
            18: 'Eighteen',
            19: 'Nineteen'
        }
        return switcher.get(num)

    def tens(num):
        switcher = {
            2: 'Twenty',
            3: 'Thirty',
            4: 'Forty',
            5: 'Fifty',
            6: 'Sixty',
            7: 'Seventy',
            8: 'Eighty',
            9: 'Ninety'
        }
        return switcher.get(num)


    def two(num):
                
        if not num:
            return ''
        elif num < 10:
            return ones(num)
        elif num < 20:
            return teens(num)
        else:
            tenner = num // 10
            rest   = num % 10
            return tens(tenner) + ' ' + ones(rest) if rest else tens(tenner)

    def three(num):
                
        hundred = num // 100
        rest    = num % 100
        
        if not hundred and rest:
            return two(rest)

        return ones(hundred) + ' Hundred ' + two(rest) if rest else ones(hundred) + ' Hundred'
        
        
    billion = num // 1000000000
    million = (num - billion * 1000000000) // 1000000
    thousand = (num - billion * 1000000000 - million * 1000000) // 1000
    rest = num % 1000

    if not num:
        return 'Zero'

    result = ''
    if billion:        
        result = three(billion) + ' Billion'
    if million:
        result += ' ' if result else ''    
        result += three(million) + ' Million'
    if thousand:
        result += ' ' if result else ''
        result += three(thousand) + ' Thousand'
    if rest:
        result += ' ' if result else ''
        result += three(rest)
    return result



num1 = 123
num2 = 12345
num3 = 1234567
num4 = 1234567891

for num in [num1, num2, num3, num4]:
    print( numberToWords(num) )

num = 1234567890
billion = num // 1000000000
million = (num - billion * 1000000000) // 1000000
thousand = (num - billion * 1000000000 - million * 1000000) // 1000
rest = num - billion * 1000000000 - million * 1000000 - thousand * 1000
print( billion, million, thousand, rest)