class Solution {
    public int findMin(int[] nums) {
        int start = 0;
        int end = nums.length-1;
        int min = Integer.MAX_VALUE;
        while(start<end){
            int mid = (start+end)/2;
            if(nums[mid]<nums[end]){
                end = mid;
            }else if(nums[mid]>nums[end]){
                //need to add one otherwise will loop forever.
                start = mid + 1;
            }
        }
        return nums[start];
    }
}

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import javax.imageio.ImageTranscoder;

class Solution {
	//main idea is topological sort.
	public boolean canFinish(int numCourses, int[][] prerequisites) {
		int[][] graph = new int[numCourses][numCourses];
		int[] inDegree = new int[numCourses];

		for(int i=0;i<prerequisites.length;i++){
			int cur = prerequisites[i][0];
			int pre = prerequisites[i][1];
			//to prevent duplication.
			if(graph[pre][cur]==0){
				inDegree[cur]++;
			}
			graph[pre][cur] = 1;

		}

		int count = 0;
		Queue<Integer> queue = new LinkedList<>();
		for(int i =0;i<numCourses;i++){
			if(inDegree[i]==0){
				queue.offer(i);
			}
		}

		while (!queue.isEmpty()){
			int course = queue.poll();
			count++;
			for(int i = 0;i<numCourses;i++){
				if(graph[course][i]!=0){
					if(--inDegree[i]==0){
						queue.offer(i);
					}
				}
			}

		}
		return count == numCourses;
	}
}

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {}

    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {

	public Node flatten(Node head) {
		if(head == null){
			return head;
		}
		Node temp = head;
		while(temp!=null){
			if(temp.child == null){
				temp = temp.next;
				continue;
			}
			Node c = flatten(temp.child);
			Node tempNx = temp.next;
			temp.next = c;
			c.prev = temp;
			while(c.next!=null){
				c = c.next;
			}
			c.next = tempNx;
			if(tempNx!=null){
				tempNx.prev = c;
			}
            temp.child = null;
			temp = tempNx;
		}
		return head;
	}

class Solution {
    public void sortColors(int[] nums) {
        int second = nums.length-1, zero = 0;
        for(int i = 0;i<=second;i++){
            while(nums[i]==2 && i<second) swap(i,second--,nums);
            while(nums[i] == 0 && i>zero) swap(i,zero++,nums);
        }

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

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet<String> seen = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(board[i][j]!='.'){
                    String temp = "(" + board[i][j] + ")";
                if(seen.contains(i+temp) || seen.contains(temp + j) || seen.contains(i/3+temp+j/3))return false;
                seen.add(i+temp) ;
                seen.add(temp+j) ;
                seen.add(i/3+temp+j/3);
                }
            }
        }
        return true;
    }
}

public List<Integer> findDuplicates(int[] nums) {
    //use negative to store information.
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; ++i) {
            int index = Math.abs(nums[i])-1;
            if (nums[index] < 0){
                res.add(Math.abs(index+1));
                continue;
            }
            nums[index] = -nums[index];
        }
        return res;
}

//count[prefix] means how many sequences that sum%K = prefix.
//so by sum[0,j] - sum[0,i] will count sum[i,j].
public int subarraysDivByK(int[] A, int K) {
        int[] count = new int[K];
        int res = 0, prefix = 0;
        count[0] = 1;
        for (int a : A) {
            prefix = (prefix + a % K + K) % K;
            res += count[prefix];
            count[prefix]++;
        }
        return res;
    }

class Solution {

    public int countSubstrings(String s) {
        int count = 0;
        for(int i = 0; i<s.length();i++){
            count += extendPalindrome(s,i,i);
            count += extendPalindrome(s,i,i+1);
        }
        return count;
    }

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

}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int l = countDeptLeft(root);
        int r = countDeptRight(root);
        //if it's a balanced tree, can simply calc by 2^n-1.
        if(l==r){
            return (1<<l) -1;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }

    private int countDeptLeft(TreeNode root) {
        int dep = 0;
        while (root != null) {
            root = root.left;
            dep++;
        }
        return dep;
    }

    private int countDeptRight(TreeNode root) {
        int dep = 0;
        while (root != null) {
            root = root.right;
            dep++;
        }
        return dep;
    }

}

import java.util.HashMap;

class Solution {
    public int findMaxLength(int[] nums) {
        for(int i = 0;i<nums.length;i++){
            if(nums[i]==0){
                nums[i] = -1;
            }
        }
        //store the earlist position of a sum.
        //if the sum is equal, then means the difference is 0.
        HashMap<Integer,Integer> sumAtIndex = new HashMap<>();
        int sum = 0, max = 0;
        sumAtIndex.put(0,-1);
        for(int i = 0;i<nums.length;i++){
            sum += nums[i];
            if(sumAtIndex.containsKey(sum)){
                max = Math.max(max,i-sumAtIndex.get(sum));
            }else{
                sumAtIndex.put(sum,i);
            }

        }
        return max;
    }
}

import java.util.Stack;

class Solution {

    //use stack to store previous information.
    public int[] dailyTemperatures(int[] temperatures) {
    Stack<Integer> stack = new Stack<>();
    int[] ret = new int[temperatures.length];
    for(int i = 0; i < temperatures.length; i++) {
        //go back to see if the current one is a relative warmer day to previous day.
        //if the previous day is higher, than stop cause the previous day is a closer warmer day.
        while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            ret[idx] = i - idx;
        }
        //put into stack for future use.
        //all number will pushed once, so O(N).
        stack.push(i);
    }
    return ret;
}


    //same idea but use array and only cost 5 ms which stack consume 50ms.
    public int[] dailyTemperatures(int[] T) {
        int[] stack = new int[T.length];
        int[] res = new int[T.length];
        int top = -1;
        for(int i = 0;i<T.length;i++){
            while(top>-1 && T[i]>T[stack[top]]){
                int index = stack[top--];
                res[index] = i - index;
            }
            stack[++top] = i;
        }
        return res;
    }
}

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

class Solution {

    public List<String> summaryRanges(int[] nums) {
        String arrow = "->";
        List<String> res = new ArrayList<>();
        if(nums.length==1){
            res.add(nums[0]+"");
            return res;
        }

        for(int i = 0;i<nums.length;i++){
            int pre = nums[i];
            //use while will save lots of work
            while(i+1<nums.length && nums[i+1]==nums[i]+1)i++;
            if(pre!=nums[i]){
                res.add(pre+arrow+nums[i]);
            }else{
                res.add(pre+"");
            }
        }
        return res;
    }
}

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return new int[0];
        int rowLen = matrix.length;
        int colLen = matrix[0].length;
        int row = 0, col = 0, d = 1;
        int[] res = new int[rowLen * colLen];
        for (int i = 0; i < res.length; i++) {
            res[i] = matrix[row][col];
            row -= d;
            col += d;
            //order is important
            //if reverse: row<0 && col>len => row=0 then row = 2
            if (row >= rowLen) {
                row = rowLen - 1;
                col += 2;
                d = -d;
            }
            if (col >= colLen) {
                col = colLen - 1;
                row += 2;
                d = -d;
            }
            if (row < 0) {
                row = 0;
                d = -d;
            }
            if (col < 0) {
                col = 0;
                d = -d;
            }

        }
        return res;
    }
}

//solution 1 : build a map and BFS.
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        Map<TreeNode, List<TreeNode>> map = new HashMap<>();
        buildGraph(root, null, map);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(target);
        Set<TreeNode> visited = new HashSet<>();
        while (!queue.isEmpty()) {
            if (K-- == 0) {
                return queue.stream().map(e -> e.val).collect(Collectors.toList());
            }
            Queue<TreeNode> temp = new LinkedList<>();
            while (!queue.isEmpty()) {
                TreeNode cur = queue.poll();
                visited.add(cur);
                //temp.addAll(map.getOrDefault(cur,new ArrayList<>()).stream().filter(e->!visited.contains(e)).collect(Collectors.toList()));
                if (map.containsKey(cur)) {
                    List<TreeNode> neighbor = map.get(cur);
                    for (TreeNode treeNode : neighbor) {
                        if (!visited.contains(treeNode)) temp.add(treeNode);
                    }
                }
            }
            queue = temp;
        }
        return new ArrayList<Integer>();
    }

    private void buildGraph(TreeNode root, TreeNode parent, Map<TreeNode, List<TreeNode>> map) {
        if (null == root) {
            return;
        }
        if (parent != null) {
            List<TreeNode> p = map.getOrDefault(parent, new ArrayList<TreeNode>());
            p.add(root);
            map.put(parent, p);
            List<TreeNode> t = map.getOrDefault(root, new ArrayList<TreeNode>());
            t.add(parent);
            map.put(root, t);
        }
        buildGraph(root.left, root, map);
        buildGraph(root.right, root, map);
    }


//solution 2: DFS
    Map<TreeNode, Integer> map = new HashMap<>();
        
    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
        List<Integer> res = new LinkedList<>();
        find(root, target);
        dfs(root, target, K, map.get(root), res);
        return res;
    }
    
    //store distance on every node from root to target, and it's enough!
    //cause the dfs will take care the rest to calculate the distance.
    //As we know, if the distance from a node to target node is k, the distance from its child to the target node is k + 1.
    //unless the child node is closer to the target node which means the target node is in it's subtree.
    // find target node first and store the distance in that path that we could use it later directly
    private int find(TreeNode root, TreeNode target) {
        if (root == null) return -1;
        if (root == target) {
            map.put(root, 0);
            return 0;
        }
        int left = find(root.left, target);
        if (left >= 0) {
            map.put(root, left + 1);
            return left + 1;
        }
        int right = find(root.right, target);
        if (right >= 0) {
            map.put(root, right + 1);
            return right + 1;
        }
        return -1;
    }
    
    private void dfs(TreeNode root, TreeNode target, int K, int length, List<Integer> res) {
        if (root == null) return;
        if (map.containsKey(root)) length = map.get(root);
        if (length == K) res.add(root.val);
        dfs(root.left, target, K, length + 1, res);
        dfs(root.right, target, K, length + 1, res);
    }

//Lsum, sum of the last L elements
//Msum, sum of the last M elements
//Lmax, max sum of contiguous L elements before the last M elements.
//Mmax, max sum of contiguous M elements before the last L elements/
class Solution {
    public int maxSumTwoNoOverlap(int[] A, int L, int M) {
        for (int i = 1; i < A.length; i++) {
            A[i] += A[i - 1];
        }
        int Lmax = A[L - 1], Mmax = A[M - 1], res = A[L + M - 1];
        for (int i = L + M ; i < A.length; i++) {
            Lmax = Math.max(Lmax,A[i-M]-A[i-M-L]);
            Mmax = Math.max(Mmax, A[i-L] - A[i-M-L]);
            res = Math.max(res,Math.max(Lmax+(A[i]-A[i-M]),Mmax+(A[i]-A[i-L])));
        }
        return res;

    }
}

//cut into half.
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;
        while(fast.next!=null){
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        pre.next = null;
        TreeNode res = new TreeNode(slow.val);
        res.left = sortedListToBST(head);
        res.right = sortedListToBST(slow.next);
        return res;
    }

}

class Solution {
    public int minSubArrayLen_N(int s, int[] nums) {
        int left = 0, right = 0, sum = 0, min = Integer.MAX_VALUE;
        while (right < nums.length) {
            sum += nums[right++];
            while (sum >= s) {
                min = Math.min(min, right - left);
                sum -= nums[left++];
            }
        }
        return min == Integer.MAX_VALUE? 0: min;
    }

    public int minSubArrayLen_NLOGN(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] sums = new int[nums.length + 1];
        for (int i = 1; i <= nums.length; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
        }
        int min = Integer.MAX_VALUE;
        //see more detail about Arrays.binarySearch().
        //https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch(int[],%20int,%20int,%20int)
        for (int i = 0; i < nums.length; i++) {
            int end = Arrays.binarySearch(sums, i + 1, len + 1, sums[i] + s);
            if (end < 0) end = -end - 1;
            if (end == len + 1) break;
            min = Math.min(min, end - i);
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
}

class Solution {
    //let the tallest insert first.
    //then if the height is same, let small k goes first.
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0]? (o1[1]-o2[1]): -(o1[0]-o2[0]);
            }
        });
        List<int[]> res = new LinkedList<>();
        for(int[] pair : people){
            res.add(pair[1],pair);
        }
        return res.toArray(new int[people.length][]);
    }
}

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int len = prerequisites.length;
        int[] indegree = new int[numCourses];
        for(int[] pair : prerequisites){
            indegree[pair[0]] ++;
        }
        List<Integer> res = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        //indegree is 0 means no prerequisite course needed, just added into res.
        for(int i = 0;i<indegree.length;i++){
            if(indegree[i]==0){
                res.add(i);
                queue.offer(i);
            }
        }
        while(!queue.isEmpty()){
            //get a course that has been taken.
            int pre = queue.poll();
            for(int i = 0;i<len;i++){
                //if this course been taken, means the relative course may start being taken.
                if(prerequisites[i][1] == pre){
                    //if indegree is o means able to take this course, otherwise,
                    // there still remains prerequisite need to be taken.
                    indegree[prerequisites[i][0]]--;
                    //able to take the course.
                    if(indegree[prerequisites[i][0]]==0){
                        res.add(prerequisites[i][0]);
                        queue.offer(prerequisites[i][0]);
                    }
                }
            }
        }
        return res.size()==numCourses? res.stream().mapToInt(i->i).toArray():new int[0];
    }
}

class Twitter {

	//for global use.
	private static int timestamp;
	private Map<Integer, User> userMap;

	//internal class.
	private class Tweet {

		public int id;
		public int time;
		//to store in User class as linked List.
		public Tweet next;

		public Tweet(int id) {
			this.id = id;
			time = timestamp++;
			next = null;
		}
	}

	private class User {

		public int id;
		public Set<Integer> followed;
		//use linkedlist to store sorted by time.
		public Tweet head;

		public User(int id) {
			this.id = id;
			followed = new HashSet<Integer>();
			followed.add(this.id);
			head = null;
		}

		public void follow(int id) {
			followed.add(id);
		}

		public void unfollow(int id) {
			followed.remove(id);
		}

		public void post(int id) {
			Tweet t = new Tweet(id);
			t.next = head;
			head = t;
		}
	}

	/**
	 * Initialize your data structure here.
	 */
	public Twitter() {
		userMap = new HashMap<Integer, User>();
	}

	/**
	 * Compose a new tweet.
	 */
	public void postTweet(int userId, int tweetId) {
		if (!userMap.containsKey(userId)) {
			User u = new User(userId);
			userMap.put(userId, u);
		}
		User u = userMap.get(userId);
		u.post(tweetId);
	}

	/**
	 * Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed
	 * must be posted by users who the user followed or by the user herself. Tweets must be ordered
	 * from most recent to least recent.
	 */
	public List<Integer> getNewsFeed(int userId) {
		List<Integer> res = new LinkedList<>();
		if (!userMap.containsKey(userId)) {
			return res;
		}

		Set<Integer> users = userMap.get(userId).followed;
		PriorityQueue<Tweet> q = new PriorityQueue<>((a, b) -> (b.time - a.time));
		for (int user : users) {
			Tweet t = userMap.get(user).head;
			if (t != null) {
				q.add(t);
			}
		}
		int n = 0;
		//to receive most up-to-date tweet and put next to queue.
		while (!q.isEmpty() && n < 10) {
			Tweet t = q.poll();
			res.add(t.id);
			n++;
			if(t.next != null){
				q.offer(t.next);
			}
		}
		return res;

	}

	/**
	 * Follower follows a followee. If the operation is invalid, it should be a no-op.
	 */
	public void follow(int followerId, int followeeId) {
		if (!userMap.containsKey(followerId)) {
			User u = new User(followerId);
			userMap.put(followerId, u);
		}
		if (!userMap.containsKey(followeeId)) {
			User u = new User(followeeId);
			userMap.put(followeeId, u);
		}
		userMap.get(followerId).follow(followeeId);
	}

	/**
	 * Follower unfollows a followee. If the operation is invalid, it should be a no-op.
	 */
	public void unfollow(int followerId, int followeeId) {
		if (!userMap.containsKey(followerId) || followeeId == followerId) {
			return;
		}
		userMap.get(followerId).unfollow(followeeId);
	}
}

import java.util.*;

class LogSystem {
    private String min, max;
    private SortedMap<String, List<Integer>> map;
    private Map<String, Integer> index;

    public LogSystem() {
        min = "2000:01:01:00:00:00";
        max = "2017:12:31:23:59:59";
        map = new TreeMap<>();
        //use index map to store the index where you only need to consider.
        //ex. Year, only consider first 4 letter and the rest will be filled by min and max.
        index = new HashMap<>();
        index.put("Year", 4);
        index.put("Month", 7);
        index.put("Day", 10);
        index.put("Hour", 13);
        index.put("Minute", 16);
        index.put("Second", 19);
    }

    public void put(int id, String timestamp) {
        if (!map.containsKey(timestamp)) map.put(timestamp, new ArrayList<Integer>());
        map.get(timestamp).add(id);
    }

    public List<Integer> retrieve(String s, String e, String gra) {
        int idx = index.get(gra);
        String start = s.substring(0, idx) + min.substring(idx);
        //sortedmap.submap will exclude end, so add a tail "1" will result the returned submap
        //include the actual end but not larger than the last timestamp.
        String end = e.substring(0, idx) + max.substring(idx) + "1";
        SortedMap<String, List<Integer>> subMap = map.subMap(start, end);
        List<Integer> res = new ArrayList<>();
        for (List<Integer> l : subMap.values()) {
            res.addAll(l);
        }
        return res;
    }
}

/**
 * Your LogSystem object will be instantiated and called as such:
 * LogSystem obj = new LogSystem();
 * obj.put(id,timestamp);
 * List<Integer> param_2 = obj.retrieve(s,e,gra);
 */

import java.lang.reflect.Array;
import java.util.Arrays;

class Solution {
    public int[][] candyCrush(int[][] board) {
        boolean found = true;
        while (found) {
            found = step(board);
            if (found) move(board);
        }
        return board;
    }

    private boolean step(int[][] b) {
        boolean found = false;
        int Y = b.length;
        int X = b[0].length;
        for (int y = 0; y < Y; y++) {
            for (int x = 0; x < X; x++) {
                //have to check one by one but not skip the negative one.
                int val = Math.abs(b[y][x]);
                if (val == 0) continue;
                //looking rightside and set eliminated item as negative.
                if (x < X - 2 && Math.abs(b[y][x + 1]) == val && Math.abs(b[y][x + 2]) == val) {
                    found = true;
                    int idx = x;
                    while (idx < X && Math.abs(b[y][idx]) == val) {
                        b[y][idx++] = -val;
                    }
                }
                //looking downside and set eliminated item as negative.
                if (y < Y - 2 && Math.abs(b[y + 1][x]) == val && Math.abs(b[y + 2][x]) == val) {
                    found = true;
                    int idx = y;
                    while (idx < Y && Math.abs(b[idx][x]) == val) {
                        b[idx++][x] = -val;
                    }
                }
            }
        }
        return found;
    }

    private void move(int[][] b) {
        int Y = b.length;
        int X = b[0].length;
        //from bottom to top, only store positive number.
        for (int x = 0; x < X; x++) {
            int idx = Y - 1;
            for (int y = Y - 1; y >= 0; y--) {
                if (b[y][x] > 0) {
                    b[idx--][x] = b[y][x];
                }
            }
            //set rest as 0.
            for (int k = idx; k >= 0; k--) {
                b[k][x] = 0;
            }
        }
    }

}

class Trie {

    private class Node {

        Node[] alpha;
        boolean isEnd;

        public Node() {
            alpha = new Node[26];
            isEnd = false;
        }

        public boolean isEmpty() {
            for (int i = 0; i < 26; i++) {
                if (alpha[i] != null) {
                    return false;
                }
            }
            return true;
        }
    }

    Node root;

    /**
     * Initialize your data structure here.
     */
    public Trie() {
        root = new Node();
    }

    /**
     * Inserts a word into the trie.
     */
    public void insert(String word) {
        char[] charArray = word.toCharArray();
        Node cur = root;
        for (char c : charArray) {
            if (cur.alpha[c - 'a'] == null) {
                cur.alpha[c - 'a'] = new Node();
            }
            cur = cur.alpha[c - 'a'];
        }
        cur.isEnd = true;
    }

    /**
     * Returns if the word is in the trie.
     */
    public boolean search(String word) {
        char[] charArray = word.toCharArray();
        Node cur = root;
        for (char c : charArray) {
            if (cur.alpha[c - 'a'] == null) {
                return false;
            }
            cur = cur.alpha[c - 'a'];
        }
        return cur.isEnd;
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     */
    public boolean startsWith(String prefix) {
        char[] charArray = prefix.toCharArray();
        Node cur = root;
        for (char c : charArray) {
            if (cur.alpha[c - 'a'] == null) {
                return false;
            }
            cur = cur.alpha[c - 'a'];
        }
        return cur.isEnd || !cur.isEmpty();
    }
}

/**
 * Your Trie object will be instantiated and called as such: Trie obj = new Trie();
 * obj.insert(word); boolean param_2 = obj.search(word); boolean param_3 = obj.startsWith(prefix);
 */

import java.util.PriorityQueue;

class Solution {

    public String reorganizeString(String S) {
        int[] count = new int[26];
        int len = S.length();
        for (char c : S.toCharArray()) {
            count[c - 'a']++;
            if(count[c-'a']>(len+1)/2) return "";
        }
        //Greedy to fill the largest count letter first.
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (b[1] - a[1]));
        //do not add 0 count letter or will add every letter into res.
        for(int i =0;i<26;i++){
            if(count[i]!=0)pq.offer(new int[]{i+'a',count[i]});
        }
        StringBuilder sb = new StringBuilder();
        while(!pq.isEmpty()){
            int[] first = pq.poll();
            if(sb.length()==0 || sb.charAt(sb.length()-1)!=first[0]){
                sb.append((char)first[0]);
                if(--first[1] >0){
                    pq.add(first);
                }
            }else if(!pq.isEmpty()) {
                //if dup, go find second large letter.
                int[] sec = pq.poll();
                sb.append((char)sec[0]);
                if(--sec[1]>0){
                    pq.add(sec);
                }
                pq.add(first);
            }

        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Solution s=new Solution();
        System.out.println(s.reorganizeString("aab"));
    }
}

class Solution {

    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int count = 0;
        if (nums == null || nums.length == 0) {
            return count;
        }
        int pro = 1;
        for (int i = 0, j = 0; j < nums.length; j++) {
            //count the pre product.
            pro *= nums[j];
            //move i by one and find the max subarray that product < k;
            while (i <= j && pro >= k) {
                pro /= nums[i++];
            }
            count += (j - i + 1);
        }
        return count;
    }
}

class LRUCache {

  Node head;
  Node tail;
  Map<Integer,Node> nodeMap;
  int size;
  int capacity;


  public LRUCache(int capacity) {
    size= 0;
    this.capacity = capacity;
    this.nodeMap = new HashMap<>();

  }

//to get node from map and move to head.
  public int get(int key) {
    if(!nodeMap.containsKey(key)){
      return -1;
    }else{
      Node node = nodeMap.get(key);
      moveToStart(node);
      return node.val;
    }
  }

//put into map and evict least one.
  public void put(int key, int value) {
    if(nodeMap.containsKey(key)){
      Node node = nodeMap.get(key);
      node.val = value;
      moveToStart(node);
    }else{
      Node node = new Node(key,value);
      addStart(node);
      nodeMap.put(key,node);
      size++;
      while(size>capacity){
        int tailKey = tail.key;
        tail = tail.prev;
        tail.next = null;
        nodeMap.remove(tailKey);
        size--;
      }
    }
  }

  private class Node{
    int key;
    int val;
    Node prev;
    Node next;

    public Node(int key, int val){
      this.key = key;
      this.val = val;
    }
  }

  private void addStart(Node node){
    if(head==null){
      head = node;
      tail = node;
    }else{
      node.next = head;
      head.prev = node;
      head = node;
    }
  }

  private void moveToStart(Node node){
    if(node == head) return;
    if(node == tail){
      tail = tail.prev;
      tail.next = null;
      addStart(node);
    }else{
      node.prev.next = node.next;
      node.next.prev = node.prev;
      addStart(node);
    }
  }

}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

class Solution {

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        Map<String, Set<String>> neighbor = new HashMap<>();
        Map<String, String> names = new HashMap<>();
        Set<String> emails = new HashSet<>();
        for (List<String> account : accounts) {
            String name = account.get(0);
            for(int i=1; i<account.size(); i++){
                String email = account.get(i);
                emails.add( email );
                names.put( email, name );
                neighbor.putIfAbsent( email, new HashSet<String>() );

                if(i==1) continue;

                //build the "edge" between two adjacent email-nodes
                neighbor.get( account.get(i-1) ).add( email );
                neighbor.get( email ).add( account.get(i-1) );
            }
        }
        List<List<String>> result = new LinkedList<>();
        Set<String> visited = new HashSet<>();

        //search all email and use visited to prevent duplication.
        for(String s : emails)
            if( !visited.contains(s) ){
                visited.add(s);
                List<String> buffer = new ArrayList<String>();
                buffer.add(s);
                helper(s, neighbor, visited, buffer);
                Collections.sort(buffer);
                buffer.add(0, names.get(s));
                result.add(buffer);
            }
        return result;
    }

    //visited from one of the node, and get all it's related neighbors. that's accounted as one user.
    private void helper(String s, Map<String, Set<String>> map, Set<String> visited, List<String> buffer){
        for(String node : map.get(s))
            if( !visited.contains(node) ){
                visited.add(node);
                buffer.add(node);
                helper(node, map, visited, buffer);
            }
    }

}

class Solution {

    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length + 1][amount+1];
        dp[0][0] = 1;
        for (int i = 1; i <= coins.length; i++) {
            dp[i][0] = 1;
            for (int j = 1; j <= amount; j++) {
                //互斥事件：
                //1. use zero coins[i].
                //2. use at least one coins[i].
                dp[i][j] = dp[i-1][j] + (j - coins[i - 1] >= 0 ? dp[i][j - coins[i - 1]] : 0);
            }
        }
        return dp[coins.length][amount];
    }
}

class Solution {
        public int findPeakElement(int[] nums) {
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            if (start == end) {
                return start;
            }
            int mid1 = (start + end) / 2;
            int mid2 = mid1 + 1;
            if(nums[mid1]<nums[mid2]){
                start = mid2;
            }else{
                end = mid1;
            }
        }
        return start;
    }
}

class Solution {

    public int findDuplicate(int[] nums) {
        if (nums.length == 1) {
            return -1;
        }
        int slow = nums[0], fast = nums[nums[0]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        fast = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //use dummy to avoid nullpointerexception.
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode fast = dummy.next,slow = dummy.next,pre_slow = dummy;
        for(int i = 0;i<n;i++){
            fast = fast.next;
        }
        while(fast!=null){
            pre_slow = slow;
            slow = slow.next;
            fast = fast.next;
        }
        pre_slow.next = slow.next;
        return dummy.next;
    }
}

class Solution {

    public int minDominoRotations(int[] A, int[] B) {
        //use same array to remove dup so it will sum up to len.
        int[] countA = new int[7], countB = new int[7], same = new int[7];
        int len = A.length;
        for (int i = 0; i < len; i++) {
            countA[A[i]]++;
            countB[B[i]]++;
            if (A[i] == B[i]) {
                same[A[i]]++;
            }
        }

        for (int i = 1; i < 7; i++) {
            if(countA[i]+countB[i]-same[i]==len){
                return len - Math.max(countA[i],countB[i]);
            }
        }
        return -1;
    }
}