<repo_name>JingwenX/data-structure-algorithm<file_sep>/warm-up/lint_no627_longestPalindrome.py
#LINT NO 627 Longest Palindrome

#5 min
#time used: 25min

# abAbAbabazzz


class Solution:
    """
    @param s: a string which consists of lowercase or uppercase letters
    @return: the length of the longest palindromes that can be built
    """

    def longestPalindrome(self, s):
        """
        Given a string which consists of lowercase or uppercase letters, find the length of the longest palindromes that can be built with those letters.
        Sol:
        this can be finished in O(n). We just loop over and check if any letter comes in double, and then 
        make a list of all singles, pop it out when meets a double.
        O(52n)
        Worst case: abcdefg....ABCDEFG...abcdefg...ABCDEFG
        Cannot be determined until you meet the very last letter
        """
        if not s:
            return 0
        #init i and list
        i = 0
        singles = []
        while i < len(s):
            count_in_singles = singles.count(s[i])
            if count_in_singles > 0:
                singles.pop(singles.index(s[i]))
            else:
                singles.append(s[i])
            i += 1
        if len(singles) > 0:
            len_longest_palindrome = len(s) - len(singles) + 1
        else:
            len_longest_palindrome = len(s)
        return len_longest_palindrome

# accepted on second submission
# problem with first submission: used list.index(), which returns value error when encounter no value in list.
# problem with second submission: if "aaaa", the length calculation is wrong. <file_sep>/README.md
# data-structure-algorithm
Practice my data structure and algorithm skills. Mainly using Leetcode and Lintcode
<file_sep>/5binary_tree_and_tree_based_dfs/lint_no596minimum_subtree_v1.py
"""
596. Minimum Subtree

====
A solution using only divide and conquer
====

Description
https://www.lintcode.com/problem/minimum-subtree/description
Given a binary tree, find the subtree with minimum sum. Return the root of the subtree.

LintCode will print the subtree which root is your return node.
It's guaranteed that there is only one subtree with minimum sum and the given binary tree is not an empty tree.

Have you met this question in a real interview?  
Example
Example 1:

Input:
     1
   /   \
 -5     2
 /     /  \
0  2  -4  -5 

Output:1
Example 2:

Input:
   1
Output:1
"""

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

#v0.9
class Solution:
    """
    @param root: the root of binary tree
    @return: the root of the minimum subtree
    """
    def findSubtree(self, root):
        # write your code here
        # set up global variable
        self.min_weight = sys.maxsize
        self.min_root = None
        self.helper(root)
        return self.min_root
        
    def helper(self, root):
        """
        @return: the weight of the subtree
        """
        if root is None:
            return 0
        left_weight = self.helper(root.left)
        right_weight = self.helper(root.right)
        root_weight = left_weight + right_weight + root.val
        
        # compare with the current min to update †he current min_weight
        if root_weight < self.min_weight:
            self.min_weight = root_weight
            self.min_root = root
        return root_weight

#v1.0
class Solution:
    def findSubtree(self, root):
        min_subtree, min_weight, _ = None, sys.maxsize, 0
        min_subtree, min_weight, _ = self.helper(root)
        return min_subtree
    def helper(self, root):
        """
        @return: current minimum subtree root, current minimum subtree weight, current subtree weight.
        """

        if root is None:
            return None, sys.maxsize, 0
        # recursion function that return three parameter.
        # the key is, that the return level of the three need to be the same.
        min_subtree_l, min_subtree_weight_l, subtree_weight_l = self.helper(root.left)
        min_subtree_r, min_subtree_weight_r, subtree_weight_r = self.helper(root.right)
        root_subtree_weight = subtree_weight_l + subtree_weight_r + root.val
        """
        last method: v0.9
        we are using divide and conquer to get the sum of the subtree.
        Our helper function calculate the sum of the left, sum of the right, and return the sum of the root subtree.

        This method: v1.0
        we are using divide and conquer to get the minimum of the subtree.
        Our helper function calculate the min , and return the min of left subtree, right subtree, and root subtree.
        
        """
        # if left is the min, return the left
        cur_min_subtree_weight = min(min_subtree_weight_l, min_subtree_weight_r, root_subtree_weight)
        if min_subtree_weight_l == cur_min_subtree_weight:
            return min_subtree_l, cur_min_subtree_weight, root_subtree_weight
        if min_subtree_weight_r == cur_min_subtree_weight:
            return min_subtree_r, cur_min_subtree_weight, root_subtree_weight
        if root_subtree_weight == cur_min_subtree_weight:
            return root, cur_min_subtree_weight, root_subtree_weight

#v1.1 linghu optimization
class Solution:

    def findSubtree(self, root):
        # jw/o: here you don't have to init the parameter.
        # min_subtree, min_weight, _ = None, sys.maxsize, 0
        minimum, subtree, sum = self.helper(root)
        return subtree

    def helper(self, root):
        # jw/b: remember to have a aligned return type, if you return three things.
        if root is None:
            return sys.maxsize, None, 0 # jw: using sys.maxsize, for the default value of calculating the min
        # jw/o: variable naming. please make it as simple.
        # minimum_l: minimum weight of the subtree in the left
        # subtree_l: minimum subtree in the left
        # sum_l: sum of the left subtree
        # comment: use minimum and sum could include the meaning of weight.
        left_minimum, left_subtree, left_sum = self.helper(root.left)
        right_minimum, right_subtree, right_sum = self.helper(root.right)
        
        sum = left_sum + right_sum + root.val
        if left_minimum == min(left_minimum, right_minimum, sum):
            return left_minimum, left_subtree, sum
        if right_minimum == min(left_minimum, right_minimum, sum):
            return right_minimum, right_subtree, sum
        # jw/O: After the two ifs, you don't need a third if, instead you can just return.
        # if root_subtree_weight == cur_min_subtree_weight:
        #     return root, cur_min_subtree_weight, root_subtree_weight
        return sum, root, sum
<file_sep>/5binary_tree_and_tree_based_dfs/lint_no596.minimum_subtree.py
"""
596. Minimum Subtree
Description
https://www.lintcode.com/problem/minimum-subtree/description
Given a binary tree, find the subtree with minimum sum. Return the root of the subtree.

LintCode will print the subtree which root is your return node.
It's guaranteed that there is only one subtree with minimum sum and the given binary tree is not an empty tree.

Have you met this question in a real interview?  
Example
Example 1:

Input:
     1
   /   \
 -5     2
 / \   /  \
0   2 -4  -5 

Output:1
Example 2:

Input:
   1
Output:1
"""

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: the root of binary tree
    @return: the root of the minimum subtree
    """
    def findSubtree(self, root):
        # write your code here
        # set up global variable
        self.min_weight = sys.maxsize
        self.min_root = None
        self.helper(root)
        return self.min_root
        
    def helper(self, root):
        """
        @return: the weight of the subtree
        """
        if root is None:
            return 0
        left_weight = self.helper(root.left)
        right_weight = self.helper(root.right)
        root_weight = left_weight + right_weight + root.val
        
        # compare with the current min to update †he current min_weight
        if root_weight < self.min_weight:
            self.min_weight = root_weight
            self.min_root = root
        return root_weight<file_sep>/warm-up/lint_no13_ImplementingStrstr.py
class Solution:
    """
    @param source: 
    @param target: 
    @return: return the index
    Example 1:
    	Input: source = "source" ，target = "target"
    	Output: -1
    	
    	Explanation: 
    	If the source does not contain the target content, return - 1.    

    Example 2:
    	Input:source = "abcdabcdefg" ，target = "bcd"
    	Output: 1
    	
    	Explanation: 
    	If the source contains the target content, return the location where the target first appeared in the source.
    test 1:
        Input: source = "source", target = "sourcez"
    test 2:
        Input: source = "source", target = "source"
    first submission:
        cannot pass
        Input: source = "tartarget", target = "target"
        expected: 3
        real: -1

    """
    def strStr(self, source, target):
        # Write your code here
        # thinking: one pointer, when encounter something starting with target, then index starting from that index, until the last one is comfirmed to be align. If encounter something diff, restart the i.
        i_source = 0
        i_target = 0
        first_ocr_index = -1
        if not target:
            return 0
        #while 3 < 9 - 6 + 1; source[3] == target[0], first_ocr_index = 3.
        while i_source < len(source) - len(target) + 1:
            print(i_source)
            if source[i_source] == target[0]:
                first_ocr_index = i_source

                #check if the later ones are align
                while i_target < len(target):
                    if i_target == len(target) - 1:
                        return first_ocr_index
                    elif source[i_source] == target[i_target]:
                        i_target += 1
                        i_source += 1
                    #corner case: when new i_source cannot keep aligning, but could possibly start a new alignment.
                    elif source[i_source] == target[0]:
                        first_ocr_index = i_source
                        continue
                    else:
                        first_ocr_index = -1
                        i_source += 1
                        break
            else:
                i_source += 1
                    
        return first_ocr_index

# this one has not pass the test yet...
            <file_sep>/python_common_methos.py
str.lower 
#convert to lower case

len(str)
#check length

str[1]
#extract letter

str.isalnum
#check if is alphanumeric

0 to len(str) -1
#rmb the -1


list.index(ele)
#The method index() returns the lowest index in list that obj appears.
"""
list.index(x[, start[, end]])
Return zero-based index in the list of the first item whose value is equal to x. 

!!!!Raises a ValueError if there is no such item!!!!

The optional arguments start and end are interpreted as in the slice notation and are used to limit the search to a particular subsequence of the list. The returned index is computed relative to the beginning of the full sequence rather than the start argument.
"""

list.count(ele)
#to find some element to see if that is in a list, you can use this one instead.

palindrome problem: 
usually odd and even are different cases. Consider them seperately.

<file_sep>/5binary_tree_and_tree_based_dfs/lint_no632_find_maximum_node.py
#lint_no632 find maximum node. Not maximum subtree!!
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param: root: the root of tree
    @return: the max node
    jw/o: this method is totally divide and conquer
    """
    def maxNode(self, root):
        # write your code here
        max_node, _ = self.helper(root)
        return max_node
    def helper(self, root):
        """
        compare left_max_node, right_max_node and root, return the max_node and maximum
        @return max_node, maximum
        """
        if root is None:
        	# jw/b: remember to use lowest possible number in order to calculate a max
        	# return None, 0
            return None, -sys.maxsize - 1
        left_max_node, left_maximum = self.helper(root.left)
        right_max_node, right_maximum = self.helper(root.right)
        maximum = max(left_maximum, right_maximum, root.val)

        if left_maximum == maximum:
            return left_max_node, left_maximum
        if right_maximum == maximum:
            return right_max_node, right_maximum
        return root, root.val