class Solution {

    public List<String> generateSentences(List<List<String>> synonyms, String text) {
        Map<String, List<String>> graph = new HashMap<>();
        for (List<String> pair : synonyms) {
            graph.putIfAbsent(pair.get(0), new ArrayList<>());
            graph.putIfAbsent(pair.get(1), new ArrayList<>());
            graph.get(pair.get(0)).add(pair.get(1));
            graph.get(pair.get(1)).add(pair.get(0));
        }

        TreeSet<String> res = new TreeSet();
        Queue<String> queue = new LinkedList<>();
        queue.add(text);
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            res.add(cur);
            String[] words = cur.split("\\W+");
            for (int i = 0; i < words.length; i++) {
                String word = words[i];
                if (graph.containsKey(word)) {
                    for (String synonym : graph.get(word)) {
                        words[i] = synonym;
                        String next = String.join(" ", words);
                        if (!res.contains(next)) {
                            queue.add(next);
                        }
                    }
                }
            }
        }
        
        return new ArrayList<>(res);
    }
}

class Solution {

    Map<String, Set<String>> map = new HashMap<>();

    public List<String> generateSentences(List<List<String>> synonyms, String text) {
        //build graph.
        for (List<String> s : synonyms) {
            String a = s.get(0);
            String b = s.get(1);
            if (!map.containsKey(a)) {
                map.put(a, new HashSet<>());
            }
            if (!map.containsKey(b)) {
                map.put(b, new HashSet<>());
            }
            map.get(a).add(b);
            map.get(b).add(a);
        }
        String[] split = text.split("\\W+");
        List<String> res = new ArrayList<>();
        helper(res, split, 0, "");
        Collections.sort(res);
        return res;
    }

    public void helper(List<String> res, String[] split, int index, String cur) {
        if (index == split.length) {
            res.add(cur);
            return;
        }
        if (map.containsKey(split[index])) {
            List<String> choices = new ArrayList<>();
            //find all synonyms related to s
            dfs(split[index], new HashSet<>(), choices);
            //try to change word at index to every possible synonyms word
            for (String s : choices) {
                helper(res, split, index + 1, cur + (index == split.length - 1 ? s : s + " "));
            }
        } else {
            //if the word at index has no synonyms, just go for next.
            helper(res, split, index + 1, cur + (index == split.length - 1 ? split[index] : split[index] + " "));
        }
    }

    //get all synonyms related to s
    public void dfs(String s, Set<String> visited, List<String> choices) {
        choices.add(s);
        visited.add(s);
        for (String next : map.get(s)) {
            if (!visited.contains(next)) {
                dfs(next, visited, choices);
            }
        }
    }
}

import java.util.HashMap;

class FileSystem {

    Node root;

    public FileSystem() {
        root = new Node();
    }

    public boolean createPath(String path, int value) {
        String[] paths = path.split("/");
        Node cursor = root;
        for (int i = 1; i < paths.length - 1; i++) {
            String file = paths[i];
            if (!cursor.next.containsKey(file)) {
                return false;
            }
            cursor = cursor.next.get(file);
        }
        String file = paths[paths.length - 1];
        if (cursor.next.containsKey(file)) {
            return false;
        } else {
            cursor.next.put(file, new Node(value));
            return true;
        }

    }

    public int get(String path) {
        String[] paths = path.split("/");
        Node cursor = root;
        for (int i = 1; i < paths.length; i++) {
            String file = paths[i];
            if (!cursor.next.containsKey(file)) {
                return -1;
            }
            cursor = cursor.next.get(file);
        }
        return cursor.value==null?-1: cursor.value;
    }

    class Node {

        HashMap<String, Node> next;
        Integer value;

        Node() {
            this.next = new HashMap();
        }

        Node(int val) {
            this.next = new HashMap();
            this.value = val;
        }
    }
}

/**
 * Your FileSystem object will be instantiated and called as such: FileSystem obj = new FileSystem(); boolean param_1 = obj.createPath(path,value); int param_2
 * = obj.get(path);
 */

class FileSystem {

   Map<String, Integer> file = new HashMap<>(); 
    
    public FileSystem() {
        file.put("", -1);
    }
    
    public boolean createPath(String path, int value) {
        int idx = path.lastIndexOf("/");
        String parent = path.substring(0, idx);
        if (!file.containsKey(parent)) { return false; }
        return file.putIfAbsent(path, value) == null;   
    }
    
    public int get(String path) {
        return file.getOrDefault(path, -1);
    }
}

/**
 * Your FileSystem object will be instantiated and called as such:
 * FileSystem obj = new FileSystem();
 * boolean param_1 = obj.createPath(path,value);
 * int param_2 = obj.get(path);
 */

/**
Step 0: Get positive target value (step to get negative target is the same as to get positive value due to symmetry).
Step 1: Find the smallest step that the summation from 1 to step just exceeds or equalstarget.
Step 2: Find the difference between sum and target. The goal is to get rid of the difference to reach target. For ith move, if we switch the right move to the left, the change in summation will be 2*i less. Now the difference between sum and target has to be an even number in order for the math to check out.
Step 2.1: If the difference value is even, we can return the current step.
Step 2.2: If the difference value is odd, we need to increase the step until the difference is even (at most 2 more steps needed).
Eg:
target = 5
Step 0: target = 5.
Step 1: sum = 1 + 2 + 3 = 6 > 5, step = 3.
Step 2: Difference = 6 - 5 = 1. Since the difference is an odd value, we will not reach the target by switching any right move to the left. So we increase our step.
Step 2.2: We need to increase step by 2 to get an even difference (i.e. 1 + 2 + 3 + 4 + 5 = 15, now step = 5, difference = 15 - 5 = 10). Now that we have an even difference, we can simply switch any move to the left (i.e. change + to -) as long as the summation of the changed value equals to half of the difference. We can switch 1 and 4 or 2 and 3 or 5.
*/
class Solution {
    public int reachNumber(int target) {
        target = Math.abs(target);
        int step = 0, sum = 0;
        while(sum < target){
            step++;
            sum += step;
        }
        
        while((sum-target)%2!=0){
            step++;
            sum += step;
        }
        
        return step;
    }
}

class Solution {
    public String toHexspeak(String num) {
        HashSet<Character> set = new HashSet<Character>(Arrays.asList(new Character[]{'A','B','C','D','E','F'}));
        String hex = Long.toHexString(Long.parseLong(num)).toUpperCase();
        //System.out.println(hex);
        char[] res = hex.toCharArray();
        for(int i = 0;i<res.length;i++){
            char c = res[i];
            if(set.contains(c)){
                continue;
            }else if(c=='1'){
                res[i] = 'I';
            }else if(c=='0'){
                res[i] = 'O';
            }else{
                return "ERROR";
            }
        }
        return String.valueOf(res);
    }
}

class Solution {

    public String toHexspeak(String num) {
        StringBuilder result = new StringBuilder();
        long n = Long.parseLong(num);
        while (n > 0) {
            int currDigit = (int) (n % 16);
            if (currDigit == 0) {
                result.append('O');
            } else if (currDigit == 1) {
                result.append('I');
            } else if (10 <= currDigit) {
                result.append((char) (currDigit - 10 + 'A'));
            } else {
                return "ERROR";
            }
            n /= 16;
        }
        return result.reverse().toString();
    }
}

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(len==0){
            return 0;
        }else if(len==1){
            return nums[0];
        }
        return Math.max(maxProfit(nums,0,len-2),maxProfit(nums,1,len-1));
    }
    
    public int maxProfit(int[] nums, int start, int end){
        int[] dp = new int[nums.length];
        for(int i = start;i<=end;i++){
            dp[i] = Math.max(nums[i]+(i-2>=0?dp[i-2]:0),(i-1>=0?dp[i-1]:0));
        }
        //System.out.println(end +" "+dp[end]);
        return dp[end];
    }
}

class Solution {

    int max_length = 0;

    public int treeDiameter(int[][] edges) {
        HashMap<Integer, HashSet<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.putIfAbsent(edge[0], new HashSet<>());
            graph.putIfAbsent(edge[1], new HashSet<>());
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }
        
        dfs(0,0,graph);
        return max_length;
    }

    public int dfs(int node, int parent, HashMap<Integer, HashSet<Integer>> graph) {
        List<Integer> lengths = new ArrayList<>();
        for (int next : graph.getOrDefault(node, new HashSet<>())) {
            if (next != parent) {
                lengths.add(dfs(next, node, graph));
            }
        }
        lengths.sort((a, b) -> Integer.compare(b, a));
        if (lengths.size() >= 2) {
            max_length = Math.max(lengths.get(0) + lengths.get(1), max_length);
        }
        if (lengths.size() == 0) {
            return 1;
        }
        return lengths.get(0)+1;

    }
}

public class Solution {

    HashMap<Long,Integer> dp;

    public int integerReplacement(int n) {
        dp = new HashMap();
        return helper(n);
    }

    private int helper(long n) {
        if (dp.containsKey(n)) {
            return dp.get(n);
        }
        if (n == 1) {
            return 0;
        }
        if (n <= 0) {
            return Integer.MAX_VALUE;
        }
        int minS;
        if (n % 2 == 0) {
            minS = helper(n / 2);
        } else {
            minS = Math.min(helper(n + 1), helper(n - 1));
        }
        dp.put(n, minS+1);
        return minS+1;
    }
}

class Solution {
    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        helper(0,n,res);
        return res;
    }

    public void helper(int cur, int n, List<Integer> res){
        if(cur >n){
            return;
        }
        for(int i = 0;i<=9;i++){
            int next = cur * 10 + i;
            if(next==0){
                continue;
            }
            if(next <= n){
                res.add(next);
                helper(next,n,res);
            }else{
                return;
            }
        }
    }
}

class Solution {

    List<TreeNode> sortedArr = new ArrayList<>();

    public TreeNode balanceBST(TreeNode root) {
        inorderTraverse(root);
        return sortedArrayToBST(0, sortedArr.size() - 1);
    }

    void inorderTraverse(TreeNode root) {
        if (root == null) {
            return;
        }
        inorderTraverse(root.left);
        sortedArr.add(root);
        inorderTraverse(root.right);
    }

    TreeNode sortedArrayToBST(int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = (start + end) / 2;
        TreeNode root = sortedArr.get(mid);
        root.left = sortedArrayToBST(start, mid - 1);
        root.right = sortedArrayToBST(mid + 1, end);
        return root;
    }
}

class Solution {

    int makeVine(TreeNode grand) {
        int cnt = 0;
        var n = grand.right;
        while (n != null) {
            if (n.left != null) {
                var old_n = n;
                n = n.left;
                old_n.left = n.right;
                n.right = old_n;
                grand.right = n;
            } else {
                ++cnt;
                grand = n;
                n = n.right;
            }
        }
        return cnt;
    }

    void compress(TreeNode grand, int m) {
        var n = grand.right;
        while (m-- > 0) {
            var old_n = n;
            n = n.right;
            grand.right = n;
            old_n.right = n.left;
            n.left = old_n;
            grand = n;
            n = n.right;
        }
    }

    public TreeNode balanceBST(TreeNode root) {
        TreeNode grand = new TreeNode(0);
        grand.right = root;
        int cnt = makeVine(grand);
        int m = (int) Math.pow(2, (int) (Math.log(cnt + 1) / Math.log(2))) - 1;
        compress(grand, cnt - m);
        for (m = m / 2; m > 0; m /= 2) {
            compress(grand, m);
        }
        return grand.right;
    }
}

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        helper(root, res, 0);
        return res;
    }

    private void helper(TreeNode root, List<Integer> res, int d) {
        if (root == null) {
            return;
        }
        //expand list size
        if (d == res.size()) {
            res.add(root.val);
        } else {
            //or set value
            res.set(d, Math.max(res.get(d), root.val));
        }
        helper(root.left, res, d + 1);
        helper(root.right, res, d + 1);
    }
}

class Solution {

    public int maxWidthRamp(int[] A) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        int max_len = 0;
        for (int i = 0; i < A.length; ++i) {
            if (stack.isEmpty() || A[stack.peek()] > A[i]) {
                stack.push(i);
            }
        }
        //System.out.println(stack);
        for (int i = A.length-1; i >max_len; i--) {
            while (!stack.isEmpty() && A[stack.peek()] <= A[i]) {
                max_len = Math.max(max_len, i - stack.pop());
            }
        }
        return max_len;
    }
}

class Solution {

    public int numFriendRequests(int[] ages) {
        int[] numInAge = new int[121];
        int[] sumBeforeAge = new int[121];

        for (int age : ages) {
            numInAge[age]++;
        }
        for (int i = 1; i < 121; i++) {
            sumBeforeAge[i] = numInAge[i] + sumBeforeAge[i - 1];
        }

        int count = 0;
        for (int i = 15; i < 121; i++) {
            if(numInAge[i]==0){
                continue;
            }
            //valid B will only be someone smaller or equal than A and larger than A/2+7
            int num = sumBeforeAge[i] - sumBeforeAge[i / 2 + 7];
            //A will not friend themselves, so - numsInAge[i].
            count += num * numInAge[i] - numInAge[i];
        }
        return count;
    }
}

class Solution {

    public boolean hasValidPath(int[][] grid) {
        int[][][] dirs = [
            [[0, -1], [0, 1]],
            [[-1, 0], [1, 0]],
            [[0, -1], [1, 0]],
            [[0, 1], [1, 0]],
            [[0, -1], [-1, 0]],
            [[0, 1], [-1, 0]]
        ];

        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});
        visited[0][0] = true;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int x = cur[0], y = cur[1];
            for (int[] dir : dirs[grid[x][y] - 1]) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[nx][ny]) {
                    continue;
                }
                for (int[] backDir : dirs[grid[nx][ny] - 1]) {
                    if (nx + backDir[0] == x && ny + backDir[1] == y) {
                        visited[nx][ny] = true;
                        q.add(new int[]{nx, ny});
                        break;
                    }
                }
            }

        }
        return visited[m - 1][n - 1];
    }
}

/**
Count smaller number left to and right to a certain number.
than for pattern 1,2,3 and number i as 2, the total number can be caled by:
(# of number smaller than i) *  (# of number larger than i)
vice versa
*/
class Solution {

    public int numTeams(int[] rating) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int[] leftSmaller = new int[rating.length];
        int[] rightSmaller = new int[rating.length];

        //count number of numbers smaller than rating[i] to its left.
        map.put(rating[0], map.getOrDefault(rating[0], 0) + 1);
        for (int i = 1; i < rating.length; i++) {
            leftSmaller[i] = map.headMap(rating[i]).size();
            map.put(rating[i], map.getOrDefault(rating[i], 0) + 1);
        }
        map = new TreeMap();

        //count number of numbers smaller than rating[i] to its right.
        map.put(rating[rating.length - 1], map.getOrDefault(rating[rating.length - 1], 0) + 1);
        for (int i = rating.length - 2; i >= 0; i--) {
            rightSmaller[i] = map.headMap(rating[i]).size();
            map.put(rating[i], map.getOrDefault(rating[i], 0) + 1);
        }
        int count = 0;
        for (int i = 1; i < rating.length - 1; i++) {
            //pattern 3,2,1
            count += (i - leftSmaller[i]) * rightSmaller[i];
            //pattern 1,2,3
            count += leftSmaller[i] * (rating.length - 1 - i - rightSmaller[i]);
        }
        return count;
    }
}

/**
Two pattern for each row, 121 and 123.
121, the first color same as the third in a row.
123, one row has three different colors.

We consider the state of the first row,
pattern 121: 121, 131, 212, 232, 313, 323.
pattern 123: 123, 132, 213, 231, 312, 321.
So we initialize a121 = 6, a123 = 6.

We consider the next possible for each pattern:
Patter 121 can be followed by: 212, 213, 232, 312, 313
Patter 123 can be followed by: 212, 231, 312, 232

121 => three 121, two 123
123 => two 121, two 123

So we can write this dynamic programming transform equation:
b121 = a121 * 3 + a123 * 2
b123 = a121 * 2 + a123 * 2

We calculate the result iteratively
and finally return the sum of both pattern a121 + a123


Complexity
Time O(N), Space O(1)
Of course, we can do better.
O(logN) Time Solution

*/
class Solution {
    public int numOfWays(int n) {
        long a121 = 6, a123 = 6, b121, b123, mod = (long)1e9 + 7;
        for (int i = 1; i < n; ++i) {
            b121 = a121 * 3 + a123 * 2;
            b123 = a121 * 2 + a123 * 2;
            a121 = b121 % mod;
            a123 = b123 % mod;
        }
        return (int)((a121 + a123) % mod);
    }
}

class Solution {

    public boolean isPossibleDivide(int[] A, int k) {
        //must use treemap to keep it sorted, and start from smaller number.
        Map<Integer, Integer> c = new TreeMap<>();
        for (int i : A) {
            c.put(i, c.getOrDefault(i, 0) + 1);
        }
        for (int it : c.keySet()) {
            if (c.get(it) > 0) {
                for (int i = k - 1; i >= 0; --i) {
                    if (c.getOrDefault(it + i, 0) < c.get(it)) {
                        return false;
                    }
                    c.put(it + i, c.get(it + i) - c.get(it));
                }
            }
        }
        return true;
    }
}

class Solution {

    public int[] nextLargerNodes(ListNode head) {
        ArrayDeque<ListNode> stack = new ArrayDeque<>();
        HashMap<ListNode, Integer> record = new HashMap<>();
        ListNode cur = head;
        int count = 0;
        while (cur != null) {
            while (!stack.isEmpty() && stack.peek().val < cur.val) {
                record.put(stack.pop(), cur.val);
            }
            stack.push(cur);
            cur = cur.next;
            count++;
        }
        int[] res = new int[count];
        cur = head;
        int index = 0;
        while (cur != null) {
            res[index++] = record.getOrDefault(cur, 0);
            cur = cur.next;
        }

        return res;
    }
}

/**
try every possible combination and union group.
*/
class Solution {

    public int numSimilarGroups(String[] A) {
        if (A.length < 2) {
            return A.length;
        }
        int size = A.length;
        int[] parent = new int[size];
        Arrays.fill(parent, -1);
        for (int i = 0; i < size; i++) {
            for (int j = i + 1; j < size; j++) {
                //System.out.println(A[i]+" "+A[j]+" "+helper(A[i], A[j]));
                if (find(parent, i) != find(parent, j) && helper(A[i], A[j])) {
                    union(parent, i, j);
                }
            }
        }
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < size; i++) {
            set.add(find(parent, i));
        }
        //System.out.println(set);
        return set.size();
    }

    public int find(int[] parent, int num) {
        if (parent[num] == -1) {
            parent[num] = num;
        } else if (parent[num] != num) {
            parent[num] = find(parent, parent[num]);
        }
        return parent[num];
    }

    public void union(int[] parent, int num1, int num2) {
        int p1 = find(parent, num1);
        int p2 = find(parent, num2);
        if (p1 != p2) {
            parent[p2] = p1;
        }
    }

    public boolean helper(String s, String t) {
        int res = 0, i = 0;
        while (res <= 2 && i < s.length()) {
            if (s.charAt(i) != t.charAt(i)) {
                res++;
            }
            i++;
        }
        return res == 2 || res == 0;
    }
}

/**
cur contains all the prex.
*/
class Solution {

    public int subarrayBitwiseORs(int[] A) {
        Set<Integer> res = new HashSet<>(), cur = new HashSet<>(), cur2;
        for (Integer i : A) {
            cur2 = new HashSet<>();
            cur2.add(i);
            for (Integer j : cur) {
                cur2.add(i | j);
            }
            res.addAll(cur = cur2);
        }
        return res.size();
    }
}

//Count the min times a letter appears in all words.
class Solution {

    public List<String> commonChars(String[] A) {
        int[] map = new int[26];
        Arrays.fill(map, Integer.MAX_VALUE);
        for (String word : A) {
            int[] count = new int[26];
            for (char c : word.toCharArray()) {
                count[c - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                map[i] = Math.min(map[i], count[i]);
            }
        }
        List<String> res = new ArrayList<>();
        for (int i = 0; i < 26; i++) {
            while (map[i] > 0) {
                res.add("" + (char) (i + 'a'));
                map[i]--;
            }
        }
        return res;
    }
}

/**
f we look carefully, 1 & 8 ; 2 & 7; 3 & 6; 4 & 5 are practically the same.
So , problem reduces to finding max of (1,2,3,4).
And in each 1,2,3,4, values in both brackets are same, so we simply find max(value in bracket) - min(value in bracket) for each.
Then find max of values obtained from (1,2,3,4)
*/
class Solution {

    public static int maxAbsValExpr(int[] arr1, int[] arr2) {
        int max1 = Integer.MIN_VALUE;
        int max2 = Integer.MIN_VALUE;
        int max3 = Integer.MIN_VALUE;
        int max4 = Integer.MIN_VALUE;
        int min1 = Integer.MAX_VALUE;
        int min2 = Integer.MAX_VALUE;
        int min3 = Integer.MAX_VALUE;
        int min4 = Integer.MAX_VALUE;
        int n = arr1.length;
        for (int i = 0; i < n; i++) {
            // 1st scenario arr1[i] + arr2[i] + i
            max1 = Integer.max(arr1[i] + arr2[i] + i, max1);
            min1 = Integer.min(arr1[i] + arr2[i] + i, min1);
            // 2nd scenario arr1[i] + arr2[i] - i
            max2 = Integer.max(arr1[i] + arr2[i] - i, max2);
            min2 = Integer.min(arr1[i] + arr2[i] - i, min2);
            // 3rd scenario arr1[i] - arr2[i] - i
            max3 = Integer.max(arr1[i] - arr2[i] - i, max3);
            min3 = Integer.min(arr1[i] - arr2[i] - i, min3);
            // 4th scenario arr1[i] - arr2[i] + i
            max4 = Integer.max(arr1[i] - arr2[i] + i, max4);
            min4 = Integer.min(arr1[i] - arr2[i] + i, min4);
        }
        int diff1 = max1 - min1;
        int diff2 = max2 - min2;
        int diff3 = max3 - min3;
        int diff4 = max4 - min4;
        return Integer.max(Integer.max(diff1, diff2), Integer.max(diff3, diff4));
    }
}

class Solution {

    public int maxDistToClosest(int[] seats) {
        int res = 0, n = seats.length, last = -1;
        for (int i = 0; i < n; ++i) {
            if (seats[i] == 1) {
                res = last < 0 ? i : Math.max(res, (i - last) / 2);
                last = i;
            }
        }
        res = Math.max(res, n - last - 1);
        return res;
    }
}

class Solution {

    public int subarraysWithKDistinct(int[] A, int K) {
        return atMostK(A, K) - atMostK(A, K - 1);
    }

    int atMostK(int[] A, int K) {
        int i = 0, res = 0;
        Map<Integer, Integer> count = new HashMap<>();
        for (int j = 0; j < A.length; ++j) {
            if (count.getOrDefault(A[j], 0) == 0) {
                K--;
            }
            count.put(A[j], count.getOrDefault(A[j], 0) + 1);
            while (K < 0) {
                count.put(A[i], count.get(A[i]) - 1);
                if (count.get(A[i]) == 0) {
                    K++;
                }
                i++;
            }
            res += j - i + 1;
        }
        return res;
    }
}

/**
Use mod to calc, if A%k=x and B%k=k-x then (A+B) can be divided by k.

*/
class Solution {
    public boolean canArrange(int[] arr, int k) {
        int[] mod = new int[k];
        for(int num:arr){
            int temp = num % k;
            if(temp<0){
            temp+=k;}
            mod[temp]++;
        }
        if(mod[0]%2!=0){
            return false;
        }
        //be careful that i<=k/2
        //k=4 -> 1,2 | 3,4
        //k=5 -> 1,2 | 4,5 (3 is no need to check since all others are valid then 3 will always be valid.)
        for(int i = 1;i<=k/2;i++){
            if(mod[i]!=mod[k-i]){
                return false;
            }
        }
        return true;
    }
}

//up[i] and down[i] means max len ending at i that is up/down.
//up: /\/\/(ending with up)
public class Solution {
    public int wiggleMaxLength(int[] nums) {
        
        if( nums.length == 0 ) return 0;
        
        int[] up = new int[nums.length];
        int[] down = new int[nums.length];
        
        up[0] = 1;
        down[0] = 1;
        
        for(int i = 1 ; i < nums.length; i++){
            //i-1 / i 
            if( nums[i] > nums[i-1] ){
                //add (i-1,i) to sub and ending at i with up.
                up[i] = down[i-1]+1;
                //length of down will not change.
                down[i] = down[i-1];
            }else if( nums[i] < nums[i-1]){
                down[i] = up[i-1]+1;
                up[i] = up[i-1];
            }else{
                //both will not change
                down[i] = down[i-1];
                up[i] = up[i-1];
            }
        }
        
        return Math.max(down[nums.length-1],up[nums.length-1]);
    }
}

//dp[i][k] means the max result from subarray [0,i](inclusive) with k groups.
class Solution {

    double[][] memo;

    public double largestSumOfAverages(int[] A, int K) {
        int N = A.length;
        memo = new double[N][K+1];
        double cur = 0;
        for(int i =0;i<N;i++){
            cur += A[i];
            memo[i][1] = cur /(i+1);
        }
        return dp(A,N-1,K);
    }

    public double dp(int[] A, int i, int k) {
        if (memo[i][k] != 0) {
            return memo[i][k];
        }
        if (i+1 < k) {
            return 0;
        }
        double max_res = 0;
        double sum = 0;
        //divide to two part: [0,j] and (j,end]
        //[0,j] -> dp(A,j,k-1)
        //(j,end] -> sum / (i-j)
        for (int j = i - 1; j >= 0; j--) {

            sum += A[j+1];
            max_res = Math.max(max_res,dp(A,j,k-1)+sum/(i-j));
        }
        memo[i][k] = max_res;
        return max_res;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.largestSumOfAverages(new int[]{9, 1, 2, 3, 9}, 3));
    }
}

/**
sort the arrays first, so start from the largest one.
1*B + 2*C + 3*D -> 1*A + 2*B + c*C + 4*D
diff = B+C+D
keep a sum that B+C+D, then calc the max res.
*/
class Solution {

    public int maxSatisfaction(int[] satisfaction) {
        int max_res = 0;
        Arrays.sort(satisfaction);
        int cur = 0, sum = 0;
        for (int i = satisfaction.length - 1; i >= 0; i--) {
            sum += satisfaction[i];
            cur += sum;
            max_res = Math.max(max_res,cur);
        }
        return max_res;
    }
}

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i =0,j=0;
        while(i<s.length() && j<t.length()){
            if(s.charAt(i)==t.charAt(j)){
                i++;
            }
            j++;
        }
        return i==s.length();
    }
}

/**
Longest Common Subsequence.
keep orders to avoid cross link.
*/
class Solution {

    public int maxUncrossedLines(int[] A, int[] B) {
        int m = A.length, n = B.length;
        int[][] dp = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1 ; j <= n; j++) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
}

class Solution {

    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        HashMap<Integer, Integer> count = new HashMap<>();
        for (int a : A) {
            for (int b : B) {
                count.put(a + b, count.getOrDefault(a + b, 0) + 1);
            }
        }

        int res = 0;
        for (int c : C) {
            for (int d : D) {
                res += count.getOrDefault(-(c + d), 0);
            }
        }
        return res;
    }
}

/**
Sorting the input array DESC will make the DFS process run much faster. Reason behind this is we always try to put the next matchstick in the first subset. 

If there is no solution, trying a longer matchstick first will get to negative conclusion earlier. 

Runtime is improved from more than 1000ms to around 40ms. A big improvement.

*/
public class Solution {

    public boolean makesquare(int[] nums) {
        if (nums == null || nums.length < 4) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 4 != 0) {
            return false;
        }

        Arrays.sort(nums);
        reverse(nums);

        return dfs(nums, new int[4], 0, sum / 4);
    }

    private boolean dfs(int[] nums, int[] sums, int index, int target) {
        if (index == nums.length) {
            if (sums[0] == target && sums[1] == target && sums[2] == target) {
                return true;
            }
            return false;
        }

        for (int i = 0; i < 4; i++) {
            if (sums[i] + nums[index] > target) {
                continue;
            }
            sums[i] += nums[index];
            if (dfs(nums, sums, index + 1, target)) {
                return true;
            }
            sums[i] -= nums[index];
        }

        return false;
    }

    private void reverse(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i < j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            i++;
            j--;
        }
    }
}

/**
Build Trie backward, so the words sharing the same ending will be merged
Only need to count the longest word among all words sharing the same ending.
*/
class Solution {

    public int minimumLengthEncoding(String[] words) {
        TrieNode root = new TrieNode();
        List<TrieNode> leaves = new ArrayList<TrieNode>();
        for (String w : new HashSet<>(Arrays.asList(words))) {
            TrieNode cur = root;
            for (int i = w.length() - 1; i >= 0; --i) {
                char j = w.charAt(i);
                if (!cur.next.containsKey(j)) {
                    cur.next.put(j, new TrieNode());
                }
                cur = cur.next.get(j);
            }
            cur.word = w;
            leaves.add(cur);
        }
        int res = 0;
        for (TrieNode leaf : leaves) {
            if (leaf.next.isEmpty()) {
                res += leaf.word.length()+1;
            }
        }
        return res;
    }

    class TrieNode {

        HashMap<Character, TrieNode> next = new HashMap<>();
        String word;
    }
}

class Solution {
    public int minimumLengthEncoding(String[] words) {
        Set<String> s = new HashSet<>(Arrays.asList(words));
        for (String w : words) {
            StringBuilder sb = new StringBuilder();
            for (int i = w.length() - 1; i >0; i--) {
                sb.insert(0, w.charAt(i));
                s.remove(sb.toString());
            }
        }
        int res = 0;
        for (String w : s) {
            res += w.length() + 1;
        }
        return res;
    } 
}

class Solution {

    public String findLongestWord(String s, List<String> d) {
        String res = "";
        //no need to sort, simply compare and swap the res.
        //d.sort((a, b) -> (b.length() - a.length()==0?a.compareTo(b):b.length()-a.length()));
        for (int i = 0; i < d.size(); i++) {
            String word = d.get(i);
            if (isSub(word, s)) {
                if(res.length() < word.length() || (res.length() == word.length() && res.compareTo(word)>0)){
                    res = word;
                }
            }
        }
        return res;
    }

    public boolean isSub(String str1, String str2) {
        if (str2.length() < str1.length()) {
            return false;
        }
        int i = 0, j = 0;
        while (i < str1.length() && j < str2.length()) {
            if (str1.charAt(i) == str2.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == str1.length();
    }
}

/**
BFS from all the land until all visited.
travel by levels.
*/
class Solution {

    public int maxDistance(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int[][] dirs = new int[][][[0, 1], [0, -1], [1, 0], [-1, 0]];
        int m = grid.length, n = grid[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    queue.add(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }
        //special case where all 0s or all 1s, then no valid ans.
        if (queue.size() == 0 || queue.size() == m * n) {
            return -1;
        }
        int level = -1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                for (int[] dir : dirs) {
                    int nx = cur[0] + dir[0];
                    int ny = cur[1] + dir[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                        queue.add(new int[]{nx, ny});
                        visited[nx][ny] = true;
                    }
                }
            }
            level++;
        }
        return level;
    }
}

/**
Observation 1: since the order does not matter, the largest number can be formed by adding digits from largest (9) to smallest (0), e.g. 9999966330000.

Therefore, we can just count the occurrences of each digit, and then generate the string.

Observation 2: we need to use all digits to form the maximum number. If we sum all digits, and the modulo of 3 is not zero, we need to remove 1 (preferably) or 2 smallest digits. If modulo 3 of the sum is 1, for example, we will try to remove 1, 4, or 7, if exists, or two of 2, 5, or 8.
*/
class Solution {

    public String largestMultipleOfThree(int[] digits) {
        int m1[] = new int[]{1, 4, 7, 2, 5, 8}, m2[] = new int[]{2, 5, 8, 1, 4, 7};
        int sum = 0, ds[] = new int[10];
        for (int d : digits) {
            ++ds[d];
            sum += d;
        }
        //if mod is 1, then try delete 1,4,7 once.
        //if not exist, then try to delete 2,5,8 twice.
        //vice versa for mod 2.
        while (sum % 3 != 0) {
            for (int i : sum % 3 == 1 ? m1 : m2) {
                if (ds[i] > 0) {
                    --ds[i];
                    sum -= i;
                    //if delete 2,5,8, while loop will continue cause num%3!=0.
                    break;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 9; i >= 0; --i) {
            String c = Character.toString((char) ('0' + i));
            for(int j=0;j<ds[i];j++){
                sb.append(c);
            }
        }
        return sb.length() > 0 && sb.charAt(0) == '0' ? "0" : sb.toString();
    }
}