class Solution {
	//there are four situations:
	//1. digits: should count all the possible number and add to stack.
	//2. letter: just add to res.
	//3. [: should first put all the words before to resStk, then set res to empty.
	//4. ]: should start wrapping up. first get a count from countStk, then pop a string from resStk, which is the result after the [ and number.
	// then add current res, which is the result in the [], for cout times. then make the current string as res.
    public String decodeString(String s) {
        String res = "";
        Stack<Integer> countStk = new Stack();
        Stack<String> resStk = new Stack();
        int idx = 0;
        while(idx < s.length()){
            if(Character.isDigit(s.charAt(idx))){
                int count = 0;
                while(Character.isDigit(s.charAt(idx))){
                    count = count * 10 + (s.charAt(idx)-'0');
                    idx++;
                }
                countStk.push(count);
            }else if(s.charAt(idx) == '['){
                resStk.push(res);
                res = "";
                idx++;
            }else if(s.charAt(idx) == ']'){
                StringBuilder sb = new StringBuilder(resStk.pop());
                int count = countStk.pop();
                for(int i=0;i<count;i++){
                    sb.append(res);
                }
                res = sb.toString();
                idx++;
            }else{
                res += s.charAt(idx++);
            }
        }
        return res;
    }

    // use maxHeap. Put entry into maxHeap so we can always poll a number with largest frequency
    public List<Integer> topKFrequent2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap();
        for(int n: nums){
            map.put(n,map.getOrDefault(n,0)+1);
        }

        //PriorityQueue
        PriorityQueue<Map.Entry<Integer,Integer>> maxHeap =
            new PriorityQueue<>((a,b)->(b.getValue()-a.getValue()));

        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            maxHeap.add(entry);
        }
        List<Integer> res = new LinkedList();
        while(res.size()<k){
            Map.Entry<Integer,Integer> entry = maxHeap.poll();
            res.add(entry.getKey());
        }
        return res;
    }

	// use treeMap. Use freqncy as the key so we can get all freqencies in order
    public List<Integer> topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int n: nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }

        TreeMap<Integer,List<Integer>> freqMap = new TreeMap();
        for(int num: map.keySet()){
            int freq=  map.get(num);
            if(!freqMap.containsKey(freq)){
                freqMap.put(freq,new LinkedList());
            }
            freqMap.get(freq).add(num);
        }

        List<Integer> res = new LinkedList();
        while(res.size()<k){
            Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();
            res.addAll(entry.getValue());
        }
        return res;
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        if(intervals.length < 2){
            return intervals;
        }
        //remember to sort in order of first element.
        //normal order as increasing, should first minus second.
        Arrays.sort(intervals,(a,b)->(a[0]-b[0]));
        List<int[]> res = new ArrayList();
        //record the current interval.
        int[] pre = intervals[0];
        for(int i =1;i<intervals.length;i++){
            int[] cur = intervals[i];
            //if not overlap, then add to res and start a new record.
            if(pre[1] < cur[0]){
                res.add(pre);
                pre = cur;
            }else{
                pre[1] = Math.max(cur[1],pre[1]);
            }
        }

        res.add(pre);
        return res.toArray(new int[res.size()][]);
    }
}

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if(intervals==null || intervals.length == 0){
            return 0;
        }
        int max = 0;
        //sort start time.
        Arrays.sort(intervals,(a,b)->(a[0]-b[0]));
        //max heap for end time.
        PriorityQueue<int[]> pq = new PriorityQueue<>(intervals.length,(a,b)->(a[1]-b[1]));
        for(int i = 0;i<intervals.length;i++){
            while(!pq.isEmpty() && intervals[i][0] >= pq.peek()[1])
                //remove all not overlaped previous meeting.
                pq.poll();
            pq.offer(intervals[i]);
            //count the current overlaped meetings.
            max = Math.max(max,pq.size());
        }
        return max;
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        //if length is smaller than 3, than it cannot be valid.
        if(nums == null || nums.length < 3){
            return res;
        }
        //sort only take O(n·logn)
        Arrays.sort(nums);
        for(int i = 0;i<nums.length-2;i++){
        	//prevent duplication
            if(i == 0 || (i>0 && nums[i-1]!= nums[i])){
	            int start = i+1;
	            int end = nums.length - 1;
	            int sum = 0 - nums[i];
	            //should not stop when found one result, should keep looking.
	            while(start < end){
	            	//once found a result.
	                if(nums[start]+nums[end] == sum){
	                    res.add(Arrays.asList(nums[i],nums[start],nums[end]));
	                    //prevent duplication.
	                    while(start < end && nums[start]==nums[start+1]) start++;
	                    while(start < end && nums[end]==nums[end-1]) end--;
	                    //don't forget to move forward for next search;
	                    start++;
	                    end--;
	                }else if(nums[start]+nums[end] < sum) {
	                	//if the result is too small, than moving start to right by one will increase the sum.
	                	start++;
	                }else end--;
	            }
        }
    }
        return res;
    }
}

class Solution {
    public String[] reorderLogFiles(String[] logs) {
    	//the main idea is to create your own compare rules.
        Comparator<String> comp = new Comparator<String>(){
            @Override
            public int compare(String s1, String s2){
                String[] split1 = s1.split(" ",2);
                String[] split2 = s2.split(" ",2);
                boolean isDigit1 = Character.isDigit(split1[1].charAt(0));
                boolean isDigit2 = Character.isDigit(split2[1].charAt(0));
                //situation 1: both are letter.
                if(!isDigit1 && !isDigit2){
                    int com = split1[1].compareTo(split2[1]);
                    if(com == 0){
                    	//if ties, than compare first.
                        return split1[0].compareTo(split2[0]);
                    }else{
                    	//if not, just return.
                        return com;
                    }
                }else{
                	//if one of them is digit, than letter should be larger.
                    return isDigit1 ? (isDigit2 ? 0 : 1) : -1;
                }
            }
        };

        Arrays.sort(logs,comp);
        return logs;
    }
}

public class Solution {
private int lo, maxLen;

public String longestPalindrome(String s) {
	int len = s.length();
	if (len < 2)
		return s;

    for (int i = 0; i < len-1; i++) {
     	extendPalindrome(s, i, i);  //assume odd length, try to extend Palindrome as possible
     	extendPalindrome(s, i, i+1); //assume even length.
    }
    return s.substring(lo, lo + maxLen);
}

private void extendPalindrome(String s, int j, int k) {
	while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
		j--;
		k++;
	}
	if (maxLen < k - j - 1) {
		lo = j + 1;
		maxLen = k - j - 1;
	}
}}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode c1 = l1;
        ListNode c2 = l2;
        ListNode sentinel = new ListNode(0);
        ListNode d = sentinel;
        int sum = 0;
        while (c1 != null || c2 != null) {
            sum /= 10;
            if (c1 != null) {
                sum += c1.val;
                c1 = c1.next;
            }
            if (c2 != null) {
                sum += c2.val;
                c2 = c2.next;
            }
            d.next = new ListNode(sum % 10);
            d = d.next;
        }
        if (sum / 10 >= 1) {
            d.next = new ListNode(sum/10);
        }
        return sentinel.next;
    }
}

class Solution {
    //main idea is that whenever an island was found, use recursion to set all island to 0, so the island will only be counted once.
    public int numIslands(char[][] grid) {
        int count = 0;
        if(grid.length == 0){
            return 0;
        }
        //iterate through all nodes to find all possible island.
        for(int  i = 0;i<grid[0].length;i++){
            for(int j = 0; j<grid.length;j++){
                if(grid[j][i] == '1'){
                    count++;
                    helper(grid,i,j);
                }
            }
        }
        return count;
    }

    //the function is to use recursion to set whole island to 0.
    private void helper(char[][] grid, int x, int y){
        //invalid cord will simply return.
        if(x<0 || y<0 || x>=grid[0].length || y>= grid.length){
            return;
        }
        //set to 0.
        grid[y][x] = 0;
        //remember to check validation before check grid[y][x].
        if(x > 0 && grid[y][x-1] == '1'){
            helper(grid,x-1,y);
        }
        if(x < grid[0].length-1 && grid[y][x+1] == '1'){
            helper(grid,x+1,y);
        }
        if(y> 0 && grid[y-1][x] == '1'){
            helper(grid,x,y-1);
        }
        if(y<grid.length-1 && grid[y+1][x] == '1'){
            helper(grid,x,y+1);
        }

    }
}

//the basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string , and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward.
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s==null || s.length()==0){
            return 0;
        }
        HashMap<Character,Integer> map = new HashMap();
        int max = 0;
        for(int i = 0,j = 0;i<s.length();i++){
            if(map.containsKey(s.charAt(i))){
                j = Math.max(j,map.get(s.charAt(i))+1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-j+1);
        }
        return max;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        if(l1.val > l2.val){
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }else{
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }
    }
}

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null && l2==null){
            return null;
        }
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        ListNode dummy = new ListNode(0);
        ListNode prev = dummy;
        while(l1 !=null && l2 != null){
            if(l1.val <= l2.val){
                prev.next = l1;
                l1 = l1.next;
            }else{
                prev.next = l2;
                l2 = l2.next;
            }
            //don't forget to move prev to next.
            prev = prev.next;
        }
        if(l1 != null){
            prev.next = l1;
        }
        if(l2 != null){
            prev.next = l2;
        }
        return dummy.next;
    }
}