class Solution {

    public int numberOfSubstrings(String s) {
        int[] count = new int[3];
        int res = 0;
        int i = 0;
        char[] strArr = s.toCharArray();
        for (int j = 0; j < strArr.length; j++) {
            count[strArr[j] - 'a']++;
            while (count[0] > 0 && count[1] > 0 && count[2] > 0) {
                count[strArr[i++] - 'a']--;
            }
            //For left in range [0, i - 1], all substring A[left]-A[right] work.
            res += i;
        }
        return res;
    }
}

import java.util.Stack;

/**
inorder successor is minimum value(leftmost value) in it's right subbtree
or if right subtree doesn't exist, it will be first left node from current node till root
 */
class Solution {


    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode succ = null;
        //try to find the min value which is larger than p.
        while (root != null) {
            if (p.val < root.val) {
                succ = root;
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return succ;
    }


}


public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        // inorder successor is minimum value(leftmost value) in it's right subbtree
        // or if right subtree doesn't exist, it will be first left node from current node
        // till root
        // CASE 1: node has right subtree
        if (p.right != null) {
            TreeNode successor = p.right;
            while(successor.left != null) successor = successor.left;
            return successor;
        }

        TreeNode ancestor = root;
        TreeNode successor = null;
        while(ancestor != null) {
            if (p.val < ancestor.val) {
                // p is in left subtree
                successor = ancestor;
                ancestor = ancestor.left;
            } else {
                // p is in right subtree
                ancestor = ancestor.right;
            }
        }
        return successor;
    }

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};
*/

class Solution {
    public Node inorderSuccessor(Node node) {
        if(node==null){
            return null;
        }

        if(node.right!=null){
            Node temp = node.right;
            while(temp!=null && temp.left!=null){
                temp = temp.left;
            }
            return temp;
        }

        Node temp = node;
        //only when cur is left subtree of parent.
        while(temp.parent!=null && temp.parent.left!=temp){
            temp = temp.parent;
        }
        temp = temp.parent;
        return temp;
    }
}

class Solution {

    public int longestCommonSubsequence(String text1, String text2) {
        //swap so less space was used.
        int len1 = text1.length(), len2 = text2.length();
        if(len1<len2){
            String temp = text2;
            text2 = text1;
            text1 = temp;
            int swap = len1;
            len1 = len2;
            len2 = swap;
        }
        
        //use two arrays instead of int[][] as dp to save space.
        int[] dp = new int[len2+1];
        int[] pre = null;

        for(int i = 1;i<=len1;i++){
            pre = Arrays.copyOf(dp,dp.length);
            for(int j = 1;j<=len2;j++){
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[j] = pre[j-1]+1;
                }else{
                    dp[j] = Math.max(pre[j],dp[j-1]);
                }
            }
        }
        return dp[len2];
    }
}

class Solution {

    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        if (S > sum || S < -sum) {
            return 0;
        }

        int[] dp = new int[2 * sum + 1];
        dp[0 + sum] = 1;
        for (int i = 0; i < nums.length; i++) {
            int[] next = new int[2 * sum + 1];
            for (int k = 0; k < 2 * sum + 1; k++) {
                if(dp[k]!=0){
                    next[k-nums[i]] += dp[k];
                    next[k+nums[i]] += dp[k];
                }
            }
            dp = next;
        }
        return dp[sum+S];
    }
}

class Solution {

    public int findTargetSumWays(int[] nums, int S) {
        ConcurrentHashMap<Integer,Integer> set = new ConcurrentHashMap<>();
        set.put(0,1);
        for(int num:nums){
            ConcurrentHashMap<Integer,Integer> temp = new ConcurrentHashMap<>();
            for(int n:set.keySet()){
                temp.put(n-num,temp.getOrDefault(n-num,0)+set.get(n));
                temp.put(n+num,temp.getOrDefault(n+num,0)+set.get(n));
            }
            set = temp;
        }
        return set.getOrDefault(S,0);
    }
}

/**
right is the number of the right most lighted bulb.

Iterate the input light A,
update right = max(right, A[i]).

Now we have lighted up i + 1 bulbs,
if right == i + 1,
it means that all the previous bulbs (to the left) are turned on too.
Then we increment res
*/
class Solution {
    public int numTimesAllBlue(int[] light) {
        int rightMost = 0;
        int count = 0;
        for(int i=0;i<light.length;i++){
            rightMost = Math.max(rightMost,light[i]);
            count += rightMost==i+1?1:0;
        }
        return count;
    }
}

/**
dp[t] means the furthest distance that we can get with t times of refueling.

So for every station s[i],
if the current distance dp[t] >= s[i][0], we can refuel:

dp[t + 1] = max(dp[t + 1], dp[t] + s[i][1])

In the end, we'll return the first t with dp[i] >= target,
otherwise we'll return -1.
*/
class Solution {

    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        long[] dp = new long[stations.length+1];
        dp[0] = startFuel;
        //for every station
        for(int i = 0;i<stations.length;i++){
            //try use station as less as possibe
            //only when dp[t] can reach the station we can refule, otherwise skip.
            for(int t = i;t>=0 && dp[t] >= stations[i][0];t--){
                dp[t+1] = Math.max(dp[t+1],dp[t]+stations[i][1]);
            }
        }
        
        for(int i = 0; i< dp.length;i++){
            if(dp[i] >= target){
                return i;
            }
        }
        return -1;
    }
}

class Solution {
    public int maximumProduct(int[] nums) {

        int min1 =Integer.MAX_VALUE, min2 = Integer.MAX_VALUE, min3 = Integer.MAX_VALUE;
        int max1 =Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        int tempMax,tempMin;

        //must update 3 then 2 then 1 in order.
        for(int num : nums){
            //find max/min for three number based on previous two and current number.
            if(min2!=Integer.MAX_VALUE && max2!=Integer.MIN_VALUE){
                 tempMax = max2*num;
                 tempMin = min2*num;
                max3 = Math.max(max3,Math.max(tempMax,tempMin));
                min3 = Math.min(min3,Math.min(tempMax,tempMin));
            }

            //assuming using cur number, see if can reach more than max or less than min.
            //based on the smallest number till then.
            if(min1!=Integer.MAX_VALUE && max1!=Integer.MIN_VALUE){
                 tempMax = max1*num;
                 tempMin = min1*num;
                max2 = Math.max(max2,Math.max(tempMax,tempMin));
                min2 = Math.min(min2,Math.min(tempMax,tempMin));
            }

            min1 = Math.min(min1,num);
            max1 = Math.max(max1,num);
        }
        return max3;
    }
}

/**
 * // This is MountainArray's API interface. // You should not implement it, or speculate about its implementation interface MountainArray { public int get(int
 * index) {} public int length() {} }
 */

class Solution {

    int findInMountainArray(int target, MountainArray A) {
        int n = A.length(), l, r, m, peak = 0;
        // find index of peak
        l = 0;
        r = n - 1;
        while (l < r) {
            m = (l + r) / 2;
            if (A.get(m) < A.get(m + 1)) {
                l = peak = m + 1;
            } else {
                r = m;
            }
        }
        // find target in the left of peak
        l = 0;
        r = peak;
        while (l <= r) {
            m = (l + r) / 2;
            if (A.get(m) < target) {
                l = m + 1;
            } else if (A.get(m) > target) {
                r = m - 1;
            } else {
                return m;
            }
        }
        // find target in the right of peak
        l = peak;
        r = n - 1;
        while (l <= r) {
            m = (l + r) / 2;
            if (A.get(m) > target) {
                l = m + 1;
            } else if (A.get(m) < target) {
                r = m - 1;
            } else {
                return m;
            }
        }
        return -1;
    }
}

import java.util.*;

class DinnerPlates {

    TreeMap<Integer, Deque<Integer>> map;
    TreeSet<Integer> avail;
    int capacity;

    public DinnerPlates(int capacity) {
        map = new TreeMap<>();
        avail = new TreeSet<>();
        this.capacity = capacity;
    }

    public void push(int val) {
        int index = 0;
        //if no available stack,, just add one.
        if(avail.isEmpty()){
            //if map is empty will use index 0.
            if(!map.isEmpty()){
                index = map.lastKey()+1;
            }
            avail.add(index);
        }else{
            index = avail.first();
        }

        map.putIfAbsent(index,new ArrayDeque<>());
        map.get(index).push(val);
        //in case the stack is empty.
        if(map.get(index).size()==capacity){
            avail.remove(index);
        }
    }

    public int pop() {
        //nothing to pop();
        if(map.isEmpty()){
            return -1;
        }
        return popAtStack(map.lastKey());
    }

    public int popAtStack(int index) {
        if(!map.containsKey(index)){
            return -1;
        }
        //pop the target stack.
        int res = map.get(index).pop();
        //remove if empty, so we can confirm nothing to pop when map.isEmpty;
        if(map.get(index).size()==0){
            map.remove(index);
        }
        //cur stack is definitely available after pop.
        avail.add(index);
        return res;
    }
}

/**
 * Your DinnerPlates object will be instantiated and called as such: DinnerPlates obj = new DinnerPlates(capacity); obj.push(val); int param_2 = obj.pop(); int
 * param_3 = obj.popAtStack(index);
 */

class Solution {

    public Node construct(int[][] grid) {
        int size = grid.length;
        return helper(grid, size / 2, size / 2, size);
    }

    public Node helper(int[][] grid, int i, int j, int size) {
        Node res = new Node();
        if (size < 2) {
            res.val = grid[i][j] == 1;
            res.isLeaf = true;
            return res;
        }
        if (size == 2) {
            if (grid[i - 1][j - 1] == grid[i][j - 1] &&
                grid[i][j - 1] == grid[i - 1][j] &&
                grid[i - 1][j] == grid[i][j]) {
                res.val = grid[i][j] == 1;
                res.isLeaf = true;
                return res;
            } else {
                res.topLeft = new Node((grid[i - 1][j - 1] == 1), true);
                res.topRight = new Node((grid[i - 1][j] == 1), true);
                res.bottomLeft = new Node((grid[i][j - 1] == 1), true);
                res.bottomRight = new Node((grid[i][j] == 1), true);
                res.isLeaf = false;
                return res;
            }
        }

        size /= 2;
        res.isLeaf = false;
        res.topLeft = helper(grid, i - size / 2, j - size / 2, size);
        res.topRight = helper(grid, i - size / 2, j + size / 2, size);
        res.bottomLeft = helper(grid, i + size / 2, j - size / 2, size);
        res.bottomRight = helper(grid, i + size / 2, j + size / 2, size);

        if (res.topLeft.val == res.topRight.val && res.topRight.val == res.bottomLeft.val && res.bottomLeft.val == res.bottomRight.val 
            && res.topLeft.isLeaf
            && res.topRight.isLeaf
            && res.bottomLeft.isLeaf
            && res.bottomRight.isLeaf) {
            res.val = res.topLeft.val;
            res.isLeaf = true;
            res.topLeft = null;
            res.topRight = null;
            res.bottomLeft = null;
            res.bottomRight = null;
        }
        return res;
    }
}

import java.util.*;

class Solution {

    public int findMaximumXOR(int[] nums) {
        int maxResult = 0;
        int mask = 0;
        /*The maxResult is a record of the largest XOR we got so far. if it's 11100 at i = 2, it means
        before we reach the last two bits, 11100 is the biggest XOR we have, and we're going to explore
        whether we can get another two '1's and put them into maxResult

        This is a greedy part, since we're looking for the largest XOR, we start
        from the very begining, aka, the 31st postition of bits. */
        for (int i = 31; i >= 0; i--) {

            //The mask will grow like  100..000 , 110..000, 111..000,  then 1111...111
            //for each iteration, we only care about the left parts
            mask = mask | (1 << i);

            Set<Integer> set = new HashSet<>();
            for (int num : nums) {

/*                we only care about the left parts, for example, if i = 2, then we have
                {1100, 1000, 0100, 0000} from {1110, 1011, 0111, 0010}*/
                int leftPartOfNum = num & mask;
                set.add(leftPartOfNum);
            }

            // if i = 1 and before this iteration, the maxResult we have now is 1100,
            // my wish is the maxResult will grow to 1110, so I will try to find a candidate
            // which can give me the greedyTry;
            int greedyTry = maxResult | (1 << i);

            for (int leftPartOfNum : set) {
                //This is the most tricky part, coming from a fact that if a ^ b = c, then a ^ c = b;
                // now we have the 'c', which is greedyTry, and we have the 'a', which is leftPartOfNum
                // If we hope the formula a ^ b = c to be valid, then we need the b,
                // and to get b, we need a ^ c, if a ^ c exisited in our set, then we're good to go
                int anotherNum = leftPartOfNum ^ greedyTry;
                if (set.contains(anotherNum)) {
                    maxResult = greedyTry;
                    break;
                }
            }

            // If unfortunately, we didn't get the greedyTry, we still have our max,
            // So after this iteration, the max will stay at 1100.
        }

        return maxResult;
    }
}

class Solution {
    public String removeKdigits(String num, int k) {
        Deque<Character> stack = new ArrayDeque<>();
        int len = num.length();
        if(len==k){
            return "0";
        }
        int i = 0;

        while(i < len){
            //if the previous is larger, poll it.
            while(k>0 && !stack.isEmpty() && stack.peekFirst() > num.charAt(i)){
                stack.pollFirst();
                k--;
            }
            stack.addFirst(num.charAt(i++));
        }

        //if k is not 0, remove the last digit as it's larger than previous.
        while(k>0){
            stack.pollFirst();
            k--;
        }

        //remove head 0.
        while(!stack.isEmpty() && stack.peekLast()=='0'){
            stack.pollLast();
        }

        //construct the number from the stack
        StringBuilder sb = new StringBuilder();

        while(!stack.isEmpty())
            sb.append(stack.pollLast());

        //in case sb is 0.
        return sb.length()==0?"0":sb.toString();
    }
}

/**
If the current max so far is equals to the current index
1,0 for index 1 means previous arr can be sorted in range.
*/
class Solution {

    public int maxChunksToSorted(int[] arr) {
        int maxSoFar = arr[0];
        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            maxSoFar = Math.max(maxSoFar, arr[i]);
            if (maxSoFar == i) {
                count++;
            }
        }
        return count;
    }
}

/**
due to the characteristic, we can see each char, ACGT as a number from 0-3, which can be store using 2 digit.
so hash the current len 10 string to a integer to see if it's duplicated.
*/
class Solution {

public List<String> findRepeatedDnaSequences(String s) {
        List<String> result = new ArrayList<>();
        Set<Integer> word = new HashSet<>();
        Set<Integer> secondWord = new HashSet<>();
        int[] map = new int[26];
        map['C' - 'A'] = 1;
        map['G' - 'A'] = 2;
        map['T' - 'A'] = 3;
        int value = 0;
        for (int i = 0; i < s.length(); i++) {
            value <<= 2;
            value |= map[s.charAt(i) - 'A'];
            //mask, so the last 20 digit will be 1 and others will be 0.
            //so only the last 20 digit was compared.
            value &= 0xfffff;
            if (i < 9) {
                continue;
            }
            if (!word.add(value) && secondWord.add(value)) {
                result.add(s.substring(i - 9, i + 1));
            }
        }
        return result;
    }
}

/**
First buy everyone a ticket to A
then count for everyone if arrange it to B, how much it can refund.
Find the max refund, then the cost would be minimum.
*/
class Solution {

    public int twoCitySchedCost(int[][] costs) {
        int len = costs.length;
        int sum = 0;
        int[] refund = new int[len];
        for(int i = 0;i<len;i++){
            sum += costs[i][0];
            //if arrange i to B, how much we can get back.
            refund[i] = costs[i][1] - costs[i][0];
        }
        Arrays.sort(refund);
        for (int i = 0; i < costs.length / 2; i++) {
            sum += refund[i];
        }
        return sum;
    }
}

/**
The idea is very simple:

last bit of (odd number & even number) is 0.
when m != n, There is at least an odd number and an even number, so the last bit position result is 0.
Move m and n rigth a position.
Keep doing step 1,2,3 until m equal to n, use a factor to record the iteration time.
*/
class Solution {
    public int rangeBitwiseAnd(int m, int n) {
        if(m==0){
            return 0;
        }
        int i = 0;
        while(m!=n){
            m>>=1;
            n>>=1;
            i++;
        }
        return m<<i;
    }
}

/**
Greedy find the event that start earliest.
*/
class Solution {

    public int maxEvents(int[][] events) {
        if (events.length == 0) {
            return 0;
        }
        int n = events.length;
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        Arrays.sort(events, (a, b) -> (a[0] - b[0]));
        int maxDay = Arrays.stream(events).mapToInt(a -> a[1]).max().getAsInt();
        int count = 0;
        int i = 0;
        for (int d = 1; d <= maxDay; d++) {
            // Add new events that can attend on day `d`
            while (i < n && events[i][0] == d) {
                pq.offer(events[i++][1]);
            }
            // Remove events that are already closed
            while (!pq.isEmpty() && pq.peek() < d) {
                pq.poll();
            }
            // Use day `d` to attend to the event that closes earlier
            if (!pq.isEmpty()) {
                count++;
                pq.poll();
            }
        }
        return count;
    }
}

/**
Use stack to store the previous number, once found a greater one, push all previous number that is less that it.
and put into a map so can look up.
*/
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> index = new HashMap<>();
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        for(int num:nums2){
            while(!stack.isEmpty() && stack.peek()<num){
                index.put(stack.pop(),num);
            }
            stack.push(num);
        }
        
        int[] res = new int[nums1.length];
        for(int i = 0;i<nums1.length;i++){
            res[i] = index.getOrDefault(nums1[i],-1);
        }
        return res;
    }
}

import java.util.*;

class Solution {

    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] next = new int[n];
        Arrays.fill(next, -1);
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        // index stack
        for (int i = 0; i < n * 2; i++) {
            int num = nums[i % n];
            while (!stack.isEmpty() && nums[stack.peek()] < num) {
                next[stack.pop()] = num;
            }
            //only when i is in the original array is i need to push to stack.
            if (i < n) {
                stack.push(i);
            }
        }
        return next;
    }
}

class Solution {
    
    Map<Integer, Integer> map;
    int N;
    int res;
    public int confusingNumberII(int N) {

        map = new HashMap<>();
        map.put(0, 0);
        map.put(1, 1);
        map.put(6, 9);
        map.put(8, 8);
        map.put(9, 6);
        res = 0;
        //1^9 itself is a confising number, but we only count number has less than 9 digits.
        if (N == 1000000000) {
            res++;
            N--;
        }
        
        this.N = N;
        search(0, 0);
        return res;
    }
    
    private void search(int p, int cur) {
        //not to continue with number larger than 1^9.
        if (p > 9 || cur > N) {
            return;
        }
        if (isConfusing(cur)) {
            res++;
        }
        //no matter if it's confusing we all need to continue.
        //as 1 is not confusing but 16 and 19 is.
        for (Integer d : map.keySet()) {
            //00 is not an option.
            if (p == 0 && d == 0) {
                continue;
            }
            //add new potential digit to last position.
            search(p + 1, cur * 10 + d);
        }
    }
    
    private boolean isConfusing(int n) {
        long rot = 0;
        int tmp = n;
        while (n > 0) {
            rot = rot * 10 + map.get(n % 10);
            n /= 10;
        }
        //after rotate, the number should not equal to itslef.
        return rot != tmp;
    }
}

class Solution {
    public boolean possibleBipartition(int N, int[][] dislikes) {
        int[] color = new int[N+1];
        HashMap<Integer, HashSet<Integer>> graph = new HashMap<>();
        for(int i = 1;i<=N;i++){
            graph.put(i,new HashSet<>());
        }
        for(int[] edge:dislikes){
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        for(int i = 1;i<=N;i++){
            if(color[i]==0){
                color[i] = 1;
                if(!dfs(i,graph,color)){
                    return false;
                }
            }
        }
        return true;
    }

    public boolean dfs(int node, HashMap<Integer, HashSet<Integer>> graph, int[] color){
        boolean res = true;
        for(int neighbor:graph.get(node)){
            if(color[neighbor]!=0){
                if(color[neighbor]==color[node]){
                    return false;
                }
            }else{
                color[neighbor] = -color[node];
                res &= dfs(neighbor,graph,color);
            }
        }
        return res;
    }


}

class Solution {
    public int countShips(Sea sea, int[] topRight, int[] bottomLeft) {
        if (!sea.hasShips(topRight, bottomLeft)) return 0;
        if (topRight[0] == bottomLeft[0] && topRight[1] == bottomLeft[1]) return 1;

        int midX = (topRight[0] + bottomLeft[0])/2;
        int midY = (topRight[1] + bottomLeft[1])/2;
        //need to take care of the boundaries so no dup.
        return countShips(sea, new int[]{midX, midY}, bottomLeft) +
            countShips(sea, topRight, new int[]{midX+1, midY+1}) +
            countShips(sea, new int[]{midX, topRight[1]}, new int[]{bottomLeft[0], midY+1}) +
            countShips(sea, new int[]{topRight[0], midY}, new int[]{midX+1, bottomLeft[1]});
    }
}

/**
Use two Treemap to store player to score and score to players.
*/
class Leaderboard {

    TreeMap<Integer, Integer> player2score;
    TreeMap<Integer, HashSet<Integer>> score2player;

    public Leaderboard() {
        player2score = new TreeMap<>();
        score2player = new TreeMap<>();
    }

    public void addScore(int playerId, int score) {
        int orig = player2score.getOrDefault(playerId, 0);
        player2score.put(playerId, orig + score);
        if (orig != 0) {
            score2player.get(orig).remove(playerId);
        }
        score2player.putIfAbsent(orig + score, new HashSet<>());
        score2player.get(orig + score).add(playerId);
    }

    public int top(int K) {
        int sum = 0;

        Integer key = score2player.lastKey();
        while (K > 0) {
            HashSet<Integer> temp = score2player.get(key);
            if (K >= temp.size()) {
                sum += key * temp.size();
                K -= temp.size();
            } else {
                sum += key * K;
                K = 0;
            }
            key = score2player.floorKey(key - 1);
            if(key==null){
                break;
            }
        }

        return sum;
    }

    public void reset(int playerId) {
        if (!player2score.containsKey(playerId)) {
            return;
        }
        int orig = player2score.get(playerId);
        player2score.remove(playerId);
        score2player.get(orig).remove(playerId);
    }
}

/**
Use HashSet to store all possible transitions, there might be multiples like meal->dinner, meal -> supper
so a map would not work
*/
class Solution {

    public boolean areSentencesSimilar(String[] words1, String[] words2, List<List<String>> pairs) {
        if (words1.length != words2.length) {
            return false;
        }
        HashSet<String> set = new HashSet<>();
        for (List<String> pair : pairs) {
            set.add(pair.get(0)+"->"+pair.get(1));
            set.add(pair.get(1)+"->"+pair.get(0));
        }
        for (int i = 0; i < words1.length; i++) {
            if(!words2[i].equals(words1[i]) && !set.contains(words1[i]+"->"+words2[i])){
                return false;
            }
        }
        return true;

    }
}

/**
Use union to find a group of words with similar meaning.
*/
class Solution {

    public boolean areSentencesSimilarTwo(String[] words1, String[] words2, List<List<String>> pairs) {
        if(words1.length != words2.length){
            return false;
        }
        HashMap<String, String> parent = new HashMap<>();
        for(List<String> pair:pairs){
            union(pair.get(0),pair.get(1),parent);
        }
        for(int i = 0;i<words1.length;i++){
            if(!findParent(words1[i],parent).equals(findParent(words2[i],parent))){
                return false;
            }
        }
        return true;
    }

    public String findParent(String word, HashMap<String, String> parent) {
        parent.putIfAbsent(word,word);
        if (!parent.get(word).equals(word)) {
            parent.put(word, findParent(parent.get(word), parent));
        }
        return parent.get(word);
    }

    public void union(String word1, String word2, HashMap<String, String> parent){
        String p1 = findParent(word1,parent);
        String p2 = findParent(word2,parent);

        if(!p1.equals(p2)){
            parent.put(p1,p2);
        }
    }
}

/**
greedy way to construct the string.

For the letter has the max count, we greedily take 2 chars. 

But for the letter didn't has the max count, we just take 1 char. 

The reason is, the letter with less count, would be used as delimiter. To have the longest happy string, we want to greedily do two things.

* Use as many as possible chars which has the max count.

* To achieve 1, we need to have as many as much delimiter.

For each loop, after appending the letters to result, we re-evaluating which letter has the max count. If it is max, follow 1, append two chars, otherwise, follow 2, just append one. Then reordering the count of all letters. Doing the same until we used up all letters with less count.
*/
class Solution {

    public String longestDiverseString(int a, int b, int c) {
        PriorityQueue<Pair<Character, Integer>> pq = new PriorityQueue<>(3, (p1, p2) -> (p2.getValue() - p1.getValue()));
        //if there's 0 available, should not put into the pq.
        if (a > 0) {
            pq.add(new Pair<>('a', a));
        }
        if (b > 0) {
            pq.add(new Pair<>('b', b));
        }
        if (c > 0) {
            pq.add(new Pair<>('c', c));
        }
        StringBuilder sb = new StringBuilder();
        while (!pq.isEmpty()) {
            Pair<Character, Integer> first = pq.poll();
            //if the current one is duplicated, then we use the next one.
            //but only use once to get longest.
            if (sb.length() != 0 && sb.charAt(sb.length() - 1) == first.getKey()) {
                //there's no second option, means there's only one available
                //so there's no way to contruct, just break;
                if (pq.isEmpty()) {
                    return sb.toString();
                }
                //get the second most number.
                Pair<Character, Integer> second = pq.poll();
                sb.append(second.getKey());
                ///if it's 0, no need to push to pq.
                if (second.getValue() > 1) {
                    pq.offer(new Pair<Character, Integer>(second.getKey(), second.getValue() - 1));
                }
                pq.offer(first);
            } else {
                //always push as much as possible if it's the most number and is not equal to previous one.
                int limit = Math.min(2, first.getValue());
                for (int i = 0; i < limit; i++) {
                    sb.append(first.getKey());
                }
                if (first.getValue() - limit > 0) {
                    pq.offer(new Pair<>(first.getKey(), first.getValue() - limit));
                }
            }
        }
        return sb.toString();
    }
}

class Solution {

    public int findNthDigit(int n) {
        long cur  = 1;
        int len =1;
        long count = 9;
        while(n > len*count){
            n -= len * count;
            len++;
            count *= 10;
            cur *= 10;
        }

        cur += (n-1)/len;
        String s = Long.toString(cur);
        return s.charAt((n-1)%len)-'0';

    }
}

class Solution {
    public int pivotIndex(int[] nums) {
        if(nums.length <=2){
            return -1;
        }
        
        int sum = Arrays.stream(nums).sum();
        int left = 0;
        for(int i = 0;i<nums.length;i++){
            if(left*2+nums[i]==sum){
                return i;
            }
            left+=nums[i];
        }
        return -1;
    }
}

class Solution {

    private int[][] dirs = new int[][][[-2, -1], [-1, -2], [1, -2], [2, -1], [2, 1], [1, 2], [-1, 2], [-2, 1]];
    double[][][] dp;

    public double knightProbability(int N, int K, int r, int c) {
        dp = new double[N][N][K + 1];
        return find(N, K, r, c);
    }

    public double find(int N, int K, int r, int c) {
        if (r < 0 || r >= N || c < 0 || c >= N) {
            return 0;
        }
        if (K == 0) {
            return 1;
        }
        if (dp[r][c][K] != 0) {
            return dp[r][c][K];
        }
        double rate = 0d;
        for (int[] dir : dirs) {
            rate += 0.125 * find(N, K - 1, r + dir[0], c + dir[1]);
        }
        dp[r][c][K] = rate;
        return rate;
    }
}

class Solution {

    public int countSquares(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int[][] res = new int[matrix.length][matrix[0].length];

        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[i].length; j++) {
                if (matrix[i][j] != 0 && matrix[i - 1][j - 1] != 0 && matrix[i][j - 1] != 0 && matrix[i - 1][j] != 0) {
                    matrix[i][j] = Math.min(matrix[i - 1][j - 1], Math.min(matrix[i][j - 1], matrix[i - 1][j])) + 1;
                }
            }
        }
        
        int sum = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                sum += matrix[i][j];
            }
        }
        return sum;
    }
}

/**
Conditions:
L can only move left, and R can only move right, and they may not across
1. their order are not able to change duo to no cross constrain XLRX has no valid move.
2. L can only move left, so the L with same order, say second L,
index of the second L in start should be larger than the index of the second L in end.
same for R.
*/
class Solution {

    public boolean canTransform(String start, String end) {
        
        if(!start.replace("X","").equals(end.replace("X",""))){
            return false;
        }
        List<Integer> leftStart = new ArrayList<>();
        List<Integer> leftEnd = new ArrayList<>();
        List<Integer> rightStart = new ArrayList<>();
        List<Integer> rightEnd = new ArrayList<>();

        for (int i = 0; i < start.length(); i++) {
            if (start.charAt(i) == 'L') {
                leftStart.add(i);
            }
            if (start.charAt(i) == 'R') {
                rightStart.add(i);
            }
            if (end.charAt(i) == 'L') {
                leftEnd.add(i);
            }
            if (end.charAt(i) == 'R') {
                rightEnd.add(i);
            }
        }

        if (leftStart.size() != leftEnd.size() || rightStart.size()!=rightEnd.size()) {
            return false;
        }
        for(int i=0;i<leftStart.size();i++){
            if(leftStart.get(i) <leftEnd.get(i)){
                return false;
            }
        }
        for(int i=0;i<rightEnd.size();i++){
            if(rightStart.get(i) > rightEnd.get(i)){
                return false;
            }
        }
        return true;
    }
}

/**
Use rows, cols and diag and antidiag to store the current state.
only if the sum is 3 or -3 means there's a winner.
*/
class Solution {
    public String tictactoe(int[][] moves) {
        int size = 3;
        int player = 1;
        int[] rows = new int[3];
        int[] cols = new int[3];
        int diag=0, antiDiag = 0;
        for(int[] move : moves){
            rows[move[1]] += player;
            if(Math.abs(rows[move[1]])==3){
                return rows[move[1]]>0?"A":"B";
            }
            cols[move[0]] += player;
            if(Math.abs(cols[move[0]])==3){
                return cols[move[0]]>0?"A":"B";
            }

            if(move[0]==move[1]){
                diag += player;
                if(Math.abs(diag)==3){
                    return diag>0?"A":"B";
                }
            }

            if(move[0]+move[1]==2){
                antiDiag += player;
                if(Math.abs(antiDiag)==3){
                    return antiDiag>0?"A":"B";
                }
            }

            player = -player;
        }

        if(moves.length==9){
            return "Draw";
        }else{
            return "Pending";
        }
    }
}

import java.util.Arrays;

class Solution {

    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void mergeSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = nums[end];
        int k = start;
        int i = start;
        //k is the tail with previous valid subarray where all items are smaller than pivot.
        while (i < end) {
            if (nums[i] < pivot) {
                swap(nums, i, k);
                k++;
            }
            i++;
        }
        swap(nums, k, end);
        mergeSort(nums, start, k - 1);
        mergeSort(nums, k + 1, end);

    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

/**
Key point: only need to take care of the string with minSize greedily.
The greedy part of the solution is that, we also notice that we only need minSize since if the minSize satisfies the constraints to have distinct letters <= maxLetters any substring greater than that size would only add at max a new distinct letter.
Which esentially means that since the substring of size greater than minSize starisfies the constraint of distinct letters <= maxLetters there will be a substring of this selected substring of size minSize that'll satisfy the same constraint and the frequency of this substring will be atleast as much as the parent substring.
We also know that number of shorter substrings are more than the longer ones , thus we only need to check for substrings of minSize satisfying the condition.
*/
class Solution {

    public int maxFreq(String s, int maxLetters, int minSize, int maxSize) {
        int left = 0;
        int max_res = 0;
        HashMap<Character, Integer> count = new HashMap<>();
        HashMap<String, Integer> sMap = new HashMap<>();
        
        for(int i =0;i<s.length();i++){
            char c = s.charAt(i);
            count.put(c,count.getOrDefault(c,0)+1);
            while(left < i && i-left+1>minSize){
                char c2 = s.charAt(left);
                count.put(c2,count.get(c2)-1);
                if(count.get(c2)==0){
                    count.remove(c2);
                }
                left++;
            }
            
            if(i-left+1==minSize && count.size()<=maxLetters){
                String str = s.substring(left,i+1);
                sMap.put(str,sMap.getOrDefault(str,0)+1);
            }
        }
        if(sMap.size()==0){
            return 0;
        }
        return sMap.values().stream().max((a,b)->(a-b)).get();
    }

}

/**
Key idea is that we only need to count the max length ending with certain char.
e.g. abcd -> d, 4 -> d, cd, bcd, abcd
so it can prevent duplication.
*/
class Solution {

    public int findSubstringInWraproundString(String p) {
        int[] count = new int[26];
        int max = 0;
        for (int i = 0; i < p.length(); i++) {
            if (i > 0 && (p.charAt(i) - p.charAt(i - 1) == 1 || p.charAt(i - 1) - p.charAt(i) == 25)) {
                max++;
            } else {
                max = 1;
            }
            int ind = p.charAt(i) - 'a';
            count[ind] = Math.max(count[ind], max);
        }
        int sum = 0;
        for (int i = 0; i < 26; i++) {
            sum += count[i];
        }
        return sum;
    }
}

/**
helper function will return the deepest level in this subtree
if and only if when the deepest is the same can we find a common node.
*/
class Solution {

    TreeNode res = null;
    int deepest = 0;

    public TreeNode lcaDeepestLeaves(TreeNode root) {
        deepest = 0;
        helper(root, 0);
        return res;
    }

    private int helper(TreeNode root, int level) {
        deepest = Math.max(deepest,level);
        if (root == null) {
            return level;
        }
        
        int leftDepth = helper(root.left, level + 1);
        int rightDepth = helper(root.right, level + 1);
        
        if (leftDepth == deepest && rightDepth==deepest) {
            res = root;
        }

        return Math.max(leftDepth, rightDepth);

    }
}

/**
Define a boundary and if exceed it will return.
*/
class Solution {

    int i = 0;

    public TreeNode bstFromPreorder(int[] A) {
        return bstFromPreorder(A, Integer.MAX_VALUE);
    }

    public TreeNode bstFromPreorder(int[] A, int bound) {
        if (i == A.length || A[i] > bound) {
            return null;
        }
        TreeNode root = new TreeNode(A[i++]);
        root.left = bstFromPreorder(A, root.val);
        root.right = bstFromPreorder(A, bound);
        return root;
    }


}