//use (i/N)*100+i%N to log the position, if i-j has the same value, means they are in the same shift.
class Solution {
    public int largestOverlap(int[][] A, int[][] B) {
        int N = A.length;
        List<Integer> LA =new ArrayList(), LB = new ArrayList();
        HashMap<Integer,Integer> count = new HashMap();
        for(int i = 0; i<N*N;i++){
            if(A[i/N][i%N]==1){
                LA.add((i/N)*100+i%N);
            }
        }
        for(int i = 0; i<N*N;i++){
            if(B[i/N][i%N]==1){
                LB.add((i/N)*100+i%N);
            }
        }
        for(int i : LA){
            for(int j : LB){
                count.put(i-j, count.getOrDefault(i-j,0)+1);
            }
        }
        int res = 0;
        for(int i:count.values()){
            res = Math.max(res, i);
        }
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        if(root1==null || root2 == null) return root1==root2;
        return root1.val==root2.val &&( (flipEquiv(root1.left,root2.right) && flipEquiv(root1.right, root2.left)) || (flipEquiv(root1.left,root2.left) && flipEquiv(root1.right, root2.right)) );
    }
}



public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        Queue<TreeNode> q1 = new LinkedList<>(), q2 = new LinkedList<>();
        q1.offer(root1);
        q2.offer(root2);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            TreeNode n1 = q1.poll(), n2 = q2.poll();
            if (n1 == null || n2 == null) {
                if (n1 != n2) return false;
                else continue;
            }
            if (n1.val != n2.val) {
                return false;
            }
            if (n1.left == n2.left || n1.left != null && n2.left != null && n1.left.val == n2.left.val) {
                q1.addAll(Arrays.asList(n1.left, n1.right));
            }else {
                q1.addAll(Arrays.asList(n1.right, n1.left));
            }
            q2.addAll(Arrays.asList(n2.left, n2.right));
        }
        return q1.isEmpty() && q2.isEmpty();
    }

class Solution {
    //check every time pushed, and pop as much as possible.
    //after pushed all items, try to pop evrything.
    //check if all item in pushed and poped are used, which means nothing left in the stack.
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack();
        int i = 0,j=0;
        int pushLen = pushed.length, popLen = popped.length;
        while(i<pushLen && j<popLen){
            stack.push(pushed[i++]);
            while(j<popLen && !stack.isEmpty() && stack.peek()==popped[j]){
                stack.pop();
                j++;
            }
        }
        while(j<popLen && !stack.isEmpty() && stack.peek()==popped[j]){
                stack.pop();
                j++;
        }
        return i==pushLen && j==popLen;
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        //remove all number that's invalid.
        //only need number within range [1,n].
        for(int i = 0;i<n;i++){
            if(nums[i]<0 || nums[i]>n){
                nums[i] = 0;
            }
        }
        //since our possible numbers are in range [1,n], we can use mode n+1 to store the count information.
        //so number i will add (n+1) to nums[i-1].
        for(int i = 0;i<n;i++){
            if(nums[i]%(n+1)==0) continue;
            nums[nums[i]%(n+1)-1]+=(n+1);
        }
        //the first time we meet nums[i]/(n+1)==0 means this number has never been met before. return it.
        for(int i = 0;i<n;i++){
            if(nums[i]/(n+1)==0){
                return i+1;
            }
        }
        return n+1;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
//main idea is to reverse the second half and compare two linkedlist.
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //if count is odd, then slow is now the middle one, move to next.
        if (fast != null) {
            slow = slow.next;
        }
        slow = reverse(slow);
        fast = head;
        //fast can only be equal or one longer than slow, so only need to take care of the slow.
         while (slow != null) {
            if (fast.val != slow.val) {
                return false;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return true;
    }
    
    public ListNode reverse(ListNode head) {
        if(head == null){
            return null;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode pre  = dummy;
        ListNode cur = dummy.next;
        ListNode than = cur.next;
        while(than != null){
            cur.next = than.next;
            than.next = pre.next;
            pre.next = than;
            than = cur.next;
        }
        return dummy.next;
        
    }
}

//main idea is to use recursion to change a k-sum problem to k-1-sum problem which end with 2-sum and using 2pointer to solve.
//4 sum, can be solved by taking a number, and solve 3-sum for the rest of the array.
class Solution {
    
    int len = 0;
    public List<List<Integer>> fourSum(int[] nums, int target) {
        len = nums.length;
        Arrays.sort(nums);
        return kSum(nums,target,4,0);
    }
    
    public List<List<Integer>> kSum(int[] nums, int target, int k, int index){
        ArrayList<List<Integer>> res=  new ArrayList();
        if(index >= len){
            return res;
        }
        if(k==2){
            int i = index, j = len-1;
            while(i<j){
                if(nums[i] + nums[j] == target){
                    List<Integer> temp = new ArrayList();
                    temp.add(nums[i]);
                    temp.add(nums[j]);
                    res.add(temp);
                    while(i<j && nums[i]==nums[i+1]){
                        i++;
                    }
                    while(i<j && nums[j]==nums[j-1]){
                        j--;
                    }
                    i++;
                    j--;
                }else if(nums[i] + nums[j] < target){
                    i++;
                }else{
                    j--;
                }
            }
        }else{
            for(int i = index;i<len-k+1;i++){
                List<List<Integer>> temp=  kSum(nums,target-nums[i],k-1,i+1);
                if(temp != null){
                    for(List<Integer> l : temp){
                        l.add(nums[i]);
                        res.add(l);
                    }
                }
                while(i<len-k+1 && nums[i]==nums[i+1]){
                    i++;
                }
            }
        }
        return res;
    }
}

//main idea is whenever the current height is lower than previous one, keep popup all previous height that's larger than cur.
//so we can sure that in the current stack, heights are ascending.
//so for position i, we can say i-1 is the max one. and we can use this max to count all previous value.
//for example, 215562, when at the end 2, 6 is the previous max, so i-s.peek()-1 will the the length which is 1.
//then we can say 5 is the next one, and i-s.peek()-1 will be 2, since 6 was poped out, and now the area is 5*2.
//then as second 5 poped out, we know i-s.peek()-1 is 3, and height is still 5, so area is 15.
//next we meet 1 which is smaller than i, so we don't pop.
//now in the stack is 1,2 , also ascending.
//need to take care the last element i = len.
class Solution {
    public int largestRectangleArea(int[] heights) {
        if(heights==null || heights.length==0) return 0;
        Stack<Integer> s = new Stack();
        int len = heights.length;
        int res = 0;
        for(int i=0;i<len;i++){
            while(!s.isEmpty() && heights[s.peek()] > heights[i]){
                int mostLeft = s.pop();
                res = Math.max(res,heights[mostLeft] * (s.isEmpty()?i:i-s.peek()-1));
            }
            s.push(i);
        }
        while(!s.isEmpty()){
                int mostLeft = s.pop();
                res = Math.max(res,heights[mostLeft] * (s.isEmpty()?len:len-s.peek()-1));
        }
        return res;
    }
}

//same idea as previous, except we keep a list h which present the max height for each col.
class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix==null || matrix.length==0 || matrix[0].length==0) return 0;
        int rLen = matrix.length;
        int cLen = matrix[0].length;
        int[] h = new int[cLen+1];
        int res = 0;
        for(int r=0; r<rLen;r++){
            Stack<Integer> s = new Stack();
            for(int i = 0;i<=cLen;i++){
                //maintain a list of height represent the current max height for each col.
                if(i<cLen){
                    if(matrix[r][i]=='1') h[i]+=1;
                    else h[i] = 0;
                }
                while(!s.isEmpty() && h[i]<h[s.peek()]){
                        int left = s.pop();
                        res = Math.max(res, h[left]*(s.isEmpty()?i:i-s.peek()-1));
                }
                s.push(i);
            }
        }
        return res;
    }
}

import java.util.*;

class Solution {

    int timer;

    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        List<Integer>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
            //build graph.
        for (List<Integer> oneConnection : connections) {
            graph[oneConnection.get(0)].add(oneConnection.get(1));
            graph[oneConnection.get(1)].add(oneConnection.get(0));
        }
        //set timer to 1 so in timeStampNode if val = 0 means unvisited.
        timer = 1;
        List<List<Integer>> res = new ArrayList<>();
        int[] timeStampAtNode = new int[n];
        connectionUtil(graph, -1, 0, timeStampAtNode, res);
        return res;
    }

    public void connectionUtil(List<Integer>[] graph, int parent, int node, int[] timeStampAtNode, List<List<Integer>> res) {
        //record the current time to this node.
        timeStampAtNode[node] = timer++;
        int curTime = timeStampAtNode[node];

        for (int next : graph[node]) {
            //prevent trace back to parent as it's undirected grapgh.
            if (next == parent) continue;
            //if child has not been visited.
            if (timeStampAtNode[next] == 0) {
                connectionUtil(graph, node, next, timeStampAtNode, res);
            }
            //child are supposed to be visited later, but if it has a smaller timestamp, means a circle.
            //how? by maintains the min value of the timestamp.
            //so all item on the same loop will have the same timestamp as min.
            timeStampAtNode[node] = Math.min(timeStampAtNode[node], timeStampAtNode[next]);
            //if curTime is strictly smaller than child, means this vertex is critical.
            if (curTime < timeStampAtNode[next]) {
                res.add(Arrays.asList(node, next));
            }
        }
    }
}

//main idea is to use HashSet to store all values and check next num is exist.
//why it's O(n): by using the trick by checking whether x-1 exist in the set, we can only iterate through the sequence once, only when this number is the start of this sequence.
//so all number will only be iterate through once.
class Solution {

    public int longestConsecutive(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();
        for(int n: nums){
            set.add(n);
        }
        int res = 0;
        for(int x : nums){
            if(!set.contains(x-1)){
                int y = x;
                while(set.contains(y)){
                    y++;
                }
                res = Math.max(res, y-x);
            }
        }
        return res;
    }
}

//no need to handle special case for 1 and 2.
//use index ==0 and == last to insert 1.
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList();
        if(numRows<=0) return res;
        for(int i = 0;i<numRows;i++){
            List<Integer> row = new ArrayList();
            for(int j = 0; j< i+1;j++){
                //will handle special case where i = 0/1 (height 1/2) .
                if(j==0 || j==i){
                    row.add(1);
                }else{
                    //when i==0, it will not go into here.
                    row.add(res.get(i-1).get(j-1)+res.get(i-1).get(j));
                }
            }
            res.add(new ArrayList(row));
        }
        return res;

    }
}

//same idea, if we have number from 1 to n, we can use (n+1) as mode and record a number by adding (n+1)
class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int n = nums.length;
        for(int i = 0;i<n;i++){
            nums[(nums[i]%(n+1))-1] += (n+1);
        }
        List<Integer> res = new ArrayList();
        for(int i = 0;i<n;i++){
            if(nums[i]/(n+1)==2) res.add(i+1);
        }
        return res;
        
    }
}

//For the first we have nums[i-1]*nums[i]*nums[i+1] for the last we have nums[-1]*nums[i]*nums[n].

//OK. Think about n balloons if i is the last one to burst, what now?

//We can see that the balloons is again separated into 2 sections. But this time since the balloon i is the last balloon of all to burst, the left and right //section now has well defined boundary and do not affect each other! Therefore we can do either recursive method with memoization or dp.
class Solution {
    public int maxCoins(int[] nums) {
        int[] nums2 = new int[nums.length+2];
        int n = 1;
        //get rid of all the element of 0.
        for(int num: nums){
            if(num>0) nums2[n++]=num;
        }
        //set head and tail as 1;
        nums2[0]= nums2[n++] = 1;
        
        //dp[i][j] means max coins can get from all balloons from i to j(excluded).
        int[][] dp = new int[n][n];
        //gap starting from 2
        for(int k = 2;k<n;k++){
            //start from head to iterate through tail.
            for(int left = 0;left<n-k;left++){
                int right = left + k;
                //search all possible position that burst last.
                for(int i = left+1;i<right;i++){
                    //find the max
                    dp[left][right] = Math.max(
                        dp[left][right],
                        //burst all in left and right, then last step is to burst the ith balloon.
                        nums2[left] * nums2[i] * nums2[right] + dp[left][i] + dp[i][right]
                    );
                }
            }
        }
        return dp[0][n-1];
    }
}

//main idea is the recursion: dp[i] = dp[i/2] + i%2
class Solution {
    public int[] countBits(int num) {
        int[] res = new int[num+1];
        for(int i =1;i<=num;i++){
            res[i] = res[i/2] + i%2;
        }
        return res;
    }
}

class Solution {
    public int maxProduct(int[] nums) {
        if(nums==null || nums.length == 0) return 0;

        int res = nums[0];
        int a_min = nums[0], a_max = nums[0];
        for(int i = 1;i<nums.length;i++){
            int preMax= a_max;
            //find the max possible value, start new / multiply pre_value(positive or negative)
            a_max = Math.max(nums[i], Math.max(a_max * nums[i], a_min * nums[i]));
            a_min = Math.min(nums[i], Math.min(preMax * nums[i], a_min * nums[i]));
            res = Math.max(res, a_max);
        }
        return res;

    }
}

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        
        for(int i = 1;i<=n;i++){
            int min = Integer.MAX_VALUE;
            for(int j = 1;j*j<=i;j++){
                min = Math.min(min, dp[i-j*j]+1);
            }
            dp[i] = min;
        }

        return dp[n];
    }
}

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle==null || triangle.size()==0){
            return 0;
        }
        if(triangle.size()==1){
            return triangle.get(0).get(0);
        }
        
        int[] A = new int[triangle.get(triangle.size()-1).size()+1];
        //A[] is acting like a pre.
        for(int i = triangle.size()-1;i>=0;i--){
           List<Integer> cur = triangle.get(i);
            for(int j = 0;j<cur.size();j++){
                //A[j] and A[j+1] has not been updated, store previous list.
                A[j] = cur.get(j) + Math.min(A[j],A[j+1]);
            }
        }
        return A[0];
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n==0) return new ArrayList();
        return build(1,n);
    }
    
    public List<TreeNode> build(int start, int end){
        List<TreeNode> res = new ArrayList();
        if(start>end){
            res.add(null);
            return res;
        } 
        //for example, build (1,2)3(4,5)
        for(int idx = start;idx<=end;idx++){
            //build all possible tree for node 1,2
            List<TreeNode> left = build(start,idx-1);
            //build all possible tree for node 4,5
            List<TreeNode> right = build(idx+1,end);
            for(TreeNode leftNode : left){
                for(TreeNode rightNode : right){
                    //use 3 to build root
                    TreeNode cur = new TreeNode(idx);
                    //append all 
                    cur.left = leftNode;
                    cur.right = rightNode;
                    res.add(cur);
                }
            }
        }
        return res;
    }
}


//another idea is to use dp together with offset.
public static List<TreeNode> generateTrees(int n) {
    List<TreeNode>[] result = new List[n + 1];
    result[0] = new ArrayList<TreeNode>();
    if (n == 0) {
        return result[0];
    }

    result[0].add(null);
    for (int len = 1; len <= n; len++) {
        result[len] = new ArrayList<TreeNode>();
        for (int j = 1; j <= len; j++) {
            for (TreeNode nodeL : result[j-1]) {
                for (TreeNode nodeR : result[len - j]) {
                    TreeNode node = new TreeNode(j);
                    node.left = nodeL;
                    node.right = clone(nodeR, j);
                    result[len].add(node);
                }
            }
        }
    }
    return result[n];
}

//use offset to copy a list of subtree from offset->len.
private static TreeNode clone(TreeNode n, int offset) {
    if (n == null) {
        return null;
    }
    TreeNode node = new TreeNode(n.val + offset);
    node.left = clone(n.left, offset);
    node.right = clone(n.right, offset);
    return node;
}

//time complexity: O(4*logn) as there are log(n) layers and each layers will have to search 4 nodes.
class NumArray {

    class TreeNode{
        int start, end;
        TreeNode left, right;
        int sum;

        TreeNode(int start, int end){
            this.start = start;
            this.end = end;
            this.left = null;
            this.right = null;
            this.sum = 0;
        }
    }
    
    public TreeNode buildTree(int[] nums, int start, int end){
        if(start>end){
            return null;
        }
    
        TreeNode cur = new TreeNode(start, end);
        if(start == end){
            cur.sum = nums[start];
        }else{
            int mid = start + (end-start)/2;
            cur.left = buildTree(nums,start, mid);
            cur.right = buildTree(nums,mid+1, end);
            cur.sum = cur.left.sum + cur.right.sum;
        }
        return cur;
    }

    TreeNode root;

    public NumArray(int[] nums) {
        root = buildTree(nums,0,nums.length-1);
    }
    
    public void update(int i, int val) {
        updateTree(root, i ,val);
    }

    public void updateTree(TreeNode root,  int pos, int val){
        if(root.start == root.end){
            root.sum = val;
        }else{
            int mid = root.start + (root.end - root.start) / 2;
            if(pos <= mid){
                updateTree(root.left,pos,val);
            }else{
                updateTree(root.right, pos, val);
            }
            root.sum = root.left.sum + root.right.sum;
        }
    }
    
    public int sumRange(int i, int j) {
        return sumTree(root,i,j);
    }

    public int sumTree(TreeNode root, int i, int j){
        if(root.start == i && root.end==j){
            return root.sum;
        }else{
            int mid = root.start + (root.end - root.start) / 2;
            if(j <= mid){
                return sumTree(root.left, i,j);
            }else if(i > mid){
                return sumTree(root.right, i ,j);
            }else{
                return sumTree(root.left,i,mid) + sumTree(root.right, mid+1,j);
            }
        }
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(i,val);
 * int param_2 = obj.sumRange(i,j);
 */

class Solution {
    public int countSubstrings(String s) {
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for(int i = 0;i<len;i++){
            dp[i][i]= true;
        }
        int count = 0;
        for(int i = 0;i<len;i++){
            count++;
            for(int j = i-1;j>=0;j--){
                if(s.charAt(i)==s.charAt(j) && (i==j+1 || dp[j+1][i-1])){
                        dp[j][i] = true;
                        count++;
                }else{
                    dp[j][i] = false;
                }
            }
        }
        return count;
    }

}

//also O(n*2) but seems faster in OJ.
class Solution {
    int len;
    public int countSubstrings(String s) {
        int count= 0;
        len = s.length();
        for(int i = 0;i<len;i++){
            count += countPali(s,i,i);
            count += countPali(s,i,i+1);
        }
        return count;
    }

    private int countPali(String s, int left, int right){
        int count=0;
        while(left >= 0 && right <len && s.charAt(left)==s.charAt(right)){
            count++;
            left--;
            right++;
        }
        return count;
    }

}

class Solution {
    public boolean divisorGame(int N) {
        //dp[i] indicates the result of the game for the given number i and for the player who started the game.
        boolean[] dp = new boolean[N+1];
        dp[0] = false;
        dp[1] = false;
        //for N, start form 2 to N;
        for(int i=2; i <= N; i++){
            //try all possible x, while x will not exceed i/2. x larger than i/2 will never have N%x==0.
            for(int j=1; j <= i/2; j++){
                if(i % j == 0){
                    //should choose the solution to let his opponent to lose.
                    if(!dp[i-j]){
                        dp[i] = true;
                        break;
                    }
                }
            }
        }
        return dp[N];
    }

    //math solution.
    public boolean divisorGame(int N) {
        return n%2==0;
    }
}

//2-> 10 + 9*9
//3-> 10 + 9*9 + 9*9*8
//4-> 10 + 9*9 + 9*9*8 + 9*9*8*7
//...
class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if(n==0) return 1;
        int res = 10;
        int uniqueDigits = 9;
        int availableNumber = 9;
        while(n-- > 1 && availableNumber > 0){
            uniqueDigits = uniqueDigits * availableNumber;
            res += uniqueDigits;
            availableNumber--;
        }
        return res;
    }
}

class Solution {
    public int numDecodings(String s) {
        int len = s.length();
        int[] dp = new int[len+1];
        dp[0] = 1;
        dp[1] = s.charAt(0)=='0'?0:1;
        for(int i = 1; i<len;i++){
            int numFirst = s.charAt(i)-'0';
            int numSec = (s.charAt(i-1)-'0')* 10 + numFirst;
            if(numFirst>=1 && numFirst<=9){
                dp[i+1] += dp[i];
            }
            if(numSec>=10 && numSec<=26){
                dp[i+1] += dp[i-1];
            }
        }
        return dp[len];
    }
}

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        if(A==null || A.length<3) return 0;
        int sum = 0;
        int cur = 0;
        for(int i = 2;i<A.length;i++){
            if(A[i-1]-A[i-2] == A[i] - A[i-1]){
                //1,2,3|4 -> 1+2= 3 total slices.
                cur++;
                sum += cur;
            }else{
                //end of slices, need to start new.
                cur = 0;
            }
        }
        return sum;
    }
}

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 1;i<=amount;i++){
            for(int coin : coins){
                if(i-coin >=0 && dp[i-coin]!=Integer.MAX_VALUE){
                    dp[i] = Math.min(dp[i], dp[i-coin]+1);
                }
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }
}

class Solution {
    public int change(int amount, int[] coins) {
        int count = coins.length;
        //dp[i][j] -> use first i coins to sum to j.
        int[][] dp = new int[count+1][amount+1];
        //for edge case: change(0,[]);
        dp[0][0] = 1;
        for(int i = 1;i<=count;i++){
            //base case: use i coins to sum to 0 is 1.
            dp[i][0] = 1;
            for(int j = 1; j<=amount;j++){
                //dp[i-1][j] -> do not use this coin, use previous i-1 coins.
                //dp[i][j-coins[i-1]] -> use the coin, and the total way to do it is to sum j-coins[i-1] with i coins.
                dp[i][j] = dp[i-1][j] + (j-coins[i-1]>=0?dp[i][j-coins[i-1]]:0);
            }
        }
        return dp[count][amount];
    }
}

class Solution {
    public boolean isInterleave(String s1, String s2, String s3) {
        int len1 = s1.length(), len2 = s2.length(), len3 = s3.length();
        if(len1 + len2 != len3) return false;
        
        boolean[][] dp = new boolean[len1+1][len2+1];

        for(int i = 0;i<=len1;i++){
            for(int j = 0;j<=len2;j++){
                if(i==0 && j==0 ){
                    dp[i][j] = true;
                }else if(i==0){
                    dp[i][j] = dp[i][j-1] && s2.charAt(j-1) == s3.charAt(j-1);
                }else if(j==0){
                    dp[i][j] = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i-1);
                }else{
                    //how to find the ribght index?
                    //use edge case like tail:
                    //dp[len1][len2] is the last of the loop, and now we have to compare the last char in s3.
                    //so we need to use s3.charAt(i+j-1), and s1.charAt(len1-1) and s2.charAt(len2-1);
                    dp[i][j] = (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1))||
                        (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1));
                }
            }
        }
        return dp[len1][len2];
    }
}

class Solution {
    //only can have two ways: end with 1 or end up in a loop;
    public boolean isHappy(int n) {
        int cur = n;
        HashSet<Integer> seen = new HashSet();
        //to check if this is a loop, if circle back, then break and return false;
        while(!seen.contains(cur)){
            int temp = 0;
            seen.add(cur);
            for(char digit: String.valueOf(cur).toCharArray()){
                temp += (digit-'0')*(digit-'0');
            }
            //meet the final result and return true.
            if(temp == 1)return true;
            cur = temp;
        }
        return false;
    }
}

class Solution {
    public String reverseWords(String s) {
        char[] ca = s.toCharArray();
        for (int i = 0; i < ca.length; i++) {
            if (ca[i] != ' ') {   // when i is a non-space
                int j = i;
                while (j + 1 < ca.length && ca[j + 1] != ' ') { j++; } // move j to the end of the word
                reverse(ca, i, j);
                i = j;
            }
        }
        return new String(ca);
    }

    private void reverse(char[] ca, int i, int j) {
        for (; i < j; i++, j--) {
            char tmp = ca[i];
            ca[i] = ca[j];
            ca[j] = tmp;
        }
    }
}

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Deque<TreeNode> st = new LinkedList();
        for(int i = 0;i<nums.length;i++){
            TreeNode cur = new TreeNode(nums[i]);
            while(!st.isEmpty() && st.peek().val < nums[i]){
                cur.left = st.pop();
            }
            if(!st.isEmpty()){
                st.peek().right = cur;
            }
            st.push(cur);
        }
        return st.isEmpty() ? null : st.removeLast();
    }
}

class Solution {
    public int islandPerimeter(int[][] grid) {
        int rLen = grid.length, cLen = grid[0].length;
        int count = 0;
        int[][] dirs = [[0,1],[1,0],[-1,0],[0,-1]];
        for(int r=0;r<rLen;r++){
            for(int c=0;c<cLen;c++){
                if(grid[r][c]==1){
                    for(int[] dir : dirs){
                        int new_r = r + dir[0];
                        int new_c = c + dir[1];
                        if(new_r<0 || new_r >= rLen || new_c<0 || new_c >= cLen||grid[new_r][new_c] == 0){
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }

}

class Solution {
    public String decodeString(String s) {
        String res = "";
        Stack<String> stack = new Stack();
        Stack<Integer> num = new Stack();
        int idx = 0;
        while(idx < s.length()){
            char c = s.charAt(idx);
            
            //find the repeat number
            if(Character.isDigit(c)){
                int count = s.charAt(idx) - '0';
                idx++;
                while(Character.isDigit(s.charAt(idx))){
                    count *= 10;
                    count += s.charAt(idx) - '0';
                    idx++;
                }
                num.push(count);
            }else if(c=='['){
                //store the previous string, and start a new one.
                stack.push(res);
                res = "";
                idx++;
            }else if(c==']'){
                //finish the current one, repeat n times and append to the previous one.
                StringBuilder sb = new StringBuilder(stack.pop());
                int repeat = num.pop();
                while(repeat-->0){
                    sb.append(res);
                }
                res = sb.toString();
                idx++;
            }else{
                //simply a char, append to res.
                res += c;
                idx++;
            }
        }
        
        return res;
    }
}

class Solution {
    public int regionsBySlashes(String[] grid) {
        int len = grid.length;
        int[][] grid_new = new int[len*3][len*3];
        for(int i = 0;i<len;i++){
            String str = grid[i];
            for(int j = 0;j<str.length();j++){
                char c = str.charAt(j);
                if(c == '\\'){
                    grid_new[j*3][i*3] = 1;
                    grid_new[j*3+1][i*3+1] = 1;
                    grid_new[j*3+2][i*3+2] = 1;
                }else if(c == '/'){
                    grid_new[j*3][i*3+2] = 1;
                    grid_new[j*3+1][i*3+1] = 1;
                    grid_new[j*3+2][i*3] = 1;
                }
            }
        }
        
        int count = 0;
        for(int i = 0;i<grid_new.length;i++){
            for(int j = 0;j<grid_new[i].length;j++){
                if(grid_new[i][j] == 0){
                    count++;
                    destroyIsland(grid_new,i,j);
                }
            }
        }
        return count;
        
    }
    
    
    private void destroyIsland(int[][] grid,int i, int j){
        if(i<0 || j < 0 || i >= grid.length || j>=grid[i].length  ||grid[i][j]!=0){
            return;
        }
        grid[i][j] = 1;
        destroyIsland(grid,i-1,j);
        destroyIsland(grid,i+1,j);
        destroyIsland(grid,i,j-1);
        destroyIsland(grid,i,j+1);
        
    }
}

class Solution {
        public static void flatten(TreeNode root) {
        if (root == null) {return;}
        flatten(root.left);
        flatten(root.right);
        TreeNode right = root.right;
        if (root.left != null) {
            root.right = root.left;
            TreeNode tail = root;
            while (tail.right != null) {
                tail = tail.right;
            }
            tail.right = right;
            root.left = null;
        }
    }

    TreeNode pre;
    public static void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flatten(root.right);
        flatten(root.left);
        
        root.right = pre;
        root.left = null;
        
        pre = root;
        
    }
}


    1
   / \
  2   5
 / \   \
3   4   6
-----------        
pre = 5
cur = 4

    1
   / 
  2   
 / \   
3   4
     \
      5
       \
        6
-----------        
pre = 4
cur = 3

    1
   / 
  2   
 /   
3 
 \
  4
   \
    5
     \
      6
-----------        
cur = 2
pre = 3

    1
   / 
  2   
   \
    3 
     \
      4
       \
        5
         \
          6
-----------        
cur = 1
pre = 2

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

class Solution {
    
    public int findCircleNum(int[][] M) {
        int[] visited = new int[M.length];
        int count = 0;
        for (int i = 0; i < M.length; i++) {
            if (visited[i] == 0) {
                dfs(M, visited, i);
                count++;
            }
        }
        return count;
    }
    
    public void dfs(int[][] M, int[] visited, int i) {
        for (int j = 0; j < M.length; j++) {
            if (M[i][j] == 1 && visited[j] == 0) {
                visited[j] = 1;
                dfs(M, visited, j);
            }
        }
    }



//another approach using union to find the common ancester.
    //slower.
    public int findCircleNum(int[][] M) {
        int[] parents = new int[M.length];
        Arrays.fill(parents, -1);
        
        for (int i = 0; i < M.length; i++) {
            for (int j = i+1; j < M.length; j++) {
                if (M[i][j] == 1 && i != j) {
                    union(parents, i, j);
                }
            }
        }
        
        int count = 0;
        for (int i = 0; i < parents.length; i++) {
            if (parents[i] == -1)
                count++;
        }
        return count;
    }
    
    public int find(int[] parents, int i){
        if(parents[i] == -1){
            return i;
        }
        return find(parents,parents[i]);
    }
    
    public void union(int[] parents, int x, int y){
        int xset = find(parents, x);
        int yset = find(parents, y);
        
        if(xset != yset){
            parents[xset] = yset;
        }
    }
}

class Solution {
    public Node connect(Node root) {
        Node level = root;
        while(level != null){
            Node cur = level;
            while(cur != null){
                if(cur.left != null){
                    cur.left.next = cur.right;
                }
                if(cur.right != null && cur.next!=null){
                    cur.right.next = cur.next.left;
                }
                cur = cur.next;
            }
            level = level.left;
        }
        return root;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
//dfs is a function to return the status of the intake root;
//0 -> leaf/ node not covered.
//1 -> middle layer, parent of a leaf, with a camera on it.
//2 -> parent of a camera, covered without a camera.
class Solution {
    int res;
    public int minCameraCover(TreeNode root) {
        res = 0;
        //if root is 0 means root not covered, add extra one.
        //res need to go behind dfs since dfs will change res.
        return (dfs(root)==0?1:0) + res;
    }
    
    public int dfs(TreeNode root){
        if(root==null) return 2;
        int left = dfs(root.left);
        int right = dfs(root.right);
        
        if(left == 0 || right == 0){
            res++;
            return 1;
        }
        
        return (left == 1 || right == 1)?2: 0;
    }
    
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int res;
    public int distributeCoins(TreeNode root) {
        res = 0;
        dfs(root);
        return res;
    }
    //dfs will return the total difference between # of node and actual money they have.
    public int dfs(TreeNode root){
        if(root==null) return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        
        //how many moves to balence
        res+= Math.abs(left);
        res+= Math.abs(right);
        
        //return the difference.
        return left+right+root.val-1;
    }
}

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *     // Constructor initializes an empty nested list.
 *     public NestedInteger();
 *
 *     // Constructor initializes a single integer.
 *     public NestedInteger(int value);
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public void setInteger(int value);
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public void add(NestedInteger ni);
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
class Solution {
    public int depthSum(List<NestedInteger> nestedList) {
        int res = 0;
        for(NestedInteger cur: nestedList){
            res += dfs(cur, 1);
        }
        return res;
    }
    
    public int dfs(NestedInteger root, int level){
        if(root.isInteger()) return root.getInteger() * level;
        int res = 0;
        for(NestedInteger cur: root.getList()){
            res += dfs(cur, level+1);
        }
        return res;
    }
}