/**
n=2 -> (4)1 (3)1 (2)1(1) 1
(x) means theres x ways to set up the pickup, or x slots to pickup after current time.
so res = res * (i * 2 - 1) * i % mod;
*/
class Solution {
    public int countOrders(int n) {
    	//use long to prevent overflow.
        long res = 1, mod = (long)1e9 + 7;
        for (int i = 1; i <= n; ++i)
            res = res * (i * 2 - 1) * i % mod;
        return (int)res;
    }
}

class Solution {

    public int numOfMinutes(final int n, final int headID, final int[] manager, final int[] informTime) {
        final Map<Integer, List<Integer>> graph = new HashMap<>();
        int total = 0;
        for (int i = 0; i < manager.length; i++) {
            int j = manager[i];
            if (!graph.containsKey(j)) {
                graph.put(j, new ArrayList<>());
            }
            graph.get(j).add(i);
        }
        return dfs(graph, informTime, headID);
    }

    private int dfs(final Map<Integer, List<Integer>> graph, final int[] informTime, final int cur) {
        int max = 0;
        if (!graph.containsKey(cur)) {
            return max;
        }
        for (int person : graph.get(cur)) {
            max = Math.max(max, dfs(graph, informTime, person));
        }
        return max + informTime[cur];
    }
}

class Solution {
    public int numPairsDivisibleBy60(int[] time) {
        int[] map  =new int[60];
        int res = 0;
        for(int t : time){
            //special case
            //if t % 60 = 0, (t % 60) % 60 = 0 instead of 60.
            res += map[(60 - t % 60) % 60];
            map[t % 60]++;
        }
        return res;
    }
}

/**
Find Longest Palindrom.

*/
class Solution {
    public boolean isValidPalindrome(String str, int k) {
        int n = str.length();

        StringBuilder stringBuilder = new StringBuilder(str).reverse();
        int lps = lcs(str, stringBuilder.toString(), n, n);

        return (n - lps <= k);
    }

    /*
    longest palindromic subsequence:
    LCS of the given string & its reverse will be the longest palindromic sequence.
     */
    private int lcs(String X, String Y, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (X.charAt(i - 1) == Y.charAt(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 boolean canThreePartsEqualSum(int[] A) {
        int sum = 0;
        for(int num:A){
            sum += num;
        }
        if(sum % 3 !=0){
            return false;
        }
        sum /= 3;
        int i =0,tempSum = 0;
        while(i < A.length){
            tempSum += A[i];
            if(tempSum == sum){
                break;
            }
            i++;
        }
        int j = A.length-1;
        tempSum = 0;
        while(j>=0){
            tempSum += A[j];
            if(tempSum == sum){
                break;
            }
            j--;
        }
        //System.out.println(i+" "+ j); 
        return j-i>1;
    }
}

class Solution {
    public boolean isOneEditDistance(String s, String t) {
        int i = 0, j = 0;
        int sLen  =s.length();
        int tLen = t.length();
        while (i < sLen && j < tLen) {
            if(s.charAt(i)!=t.charAt(j)){
                if(sLen==tLen){
                    return s.substring(i+1).equals(t.substring(j+1));
                }else if(sLen<tLen){
                    return s.substring(i).equals(t.substring(j+1));
                }else{
                    return s.substring(i+1).equals(t.substring(j));
                }
            }
            i++;
            j++;
        }
        return Math.abs(s.length() - t.length()) == 1;        
    }
}

class Solution {

    public String removeDuplicateLetters(String S) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        int[] last = new int[26];
        boolean[] seen = new boolean[26];
        for (int i = 0; i < S.length(); ++i) {
            last[S.charAt(i) - 'a'] = i;
        }
        for (int i = 0; i < S.length(); ++i) {
            int c = S.charAt(i) - 'a';
            if (seen[c]) {
                continue;
            }
            //only when the following meet can remove the previous char:
            //1. the prev char is larger than cur
            //2. It is not the last for that char.
            while (!stack.isEmpty() && stack.peek() > c && i < last[stack.peek()]) {
            	//removed from stack and pretend we never met.
                seen[stack.pop()] = false;
            }
            stack.push(c);
            seen[c] = true;
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append((char) ('a' + stack.pollLast()));
        }
        return sb.toString();
    }
}

//Count the total days between current date to 1971 and then compare.
class Solution {

    public int daysBetweenDates(String date1, String date2) {
        return Math.abs(distTo1971(date1) - distTo1971(date2));
    }

    public boolean isLeap(int year) {
        return (year % 400 == 0) || (year % 4 == 0 && year % 100 != 0);
    }

    public int distTo1971(String date) {
        int[] daysInMonth = new int[]{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        String[] dateArr = date.split("-");
        if (dateArr.length != 3) {
            return -1;
        }

        int year = Integer.parseInt(dateArr[0]);
        int month = Integer.parseInt(dateArr[1]);
        int day = Integer.parseInt(dateArr[2]);

        for (int i = 1971; i < year; i++) {
            day += isLeap(i) ? 366 : 365;
        }

        for (int i = 1; i < month; i++) {
            day += daysInMonth[i];
            if (i == 2 && isLeap(year)) {
                day++;
            }
        }

        return day;
    }
}

//use count to find the split( left +1, right -1)
//Then use recursion to resolve a valid string to tree.
class Solution {

    public TreeNode str2tree(String s) {
        if (s == null || s.isEmpty() || s.charAt(0) == '(' || s.charAt(0) == ')') {
            return null;
        }
        int index = 0;

        while (index < s.length() && (s.charAt(index) != '(' && s.charAt(index) != ')')) {
            index++;
        }
        int val = Integer.parseInt(s.substring(0, index));
        TreeNode root = new TreeNode(val);
        if (index == s.length()) {
            return root;
        }
        int count = 1;
        int leftIndex = index + 1;
        while (leftIndex < s.length() && count != 0) {
            if (s.charAt(leftIndex) == '(') {
                count++;
            } else if (s.charAt(leftIndex) == ')') {
                count--;
            }
            leftIndex++;
        }
        root.left = str2tree(s.substring(index + 1, leftIndex - 1));
        if (leftIndex != s.length()) {
            root.right = str2tree(s.substring(leftIndex + 1, s.length() - 1));
        }

        return root;
    }


}

/**
Use map to store same dialog.
*/
class Solution {

    public int[] findDiagonalOrder(List<List<Integer>> nums) {
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        int max = 0;
        for (int i = 0; i < nums.size(); i++) {
            List<Integer> list = nums.get(i);
            for (int j = 0; j < list.size(); j++) {
                map.putIfAbsent(i+j,new ArrayList<>());
                map.get(i+j).add(0,list.get(j));
                max = Math.max(max,i+j);
            }
        }
        List<Integer> res = new ArrayList<>();
        for(int i = 0;i<=max;i++){
            res.addAll(map.getOrDefault(i,new ArrayList<>()));
        }
        return res.stream().mapToInt(i->i).toArray();
    }
}

/**
We can solve this problem using Dynamic programming. Let dp[i][j] denotes the number of steps it takes to delete the substring s[i, j]. Each character will be deleted alone or as part of some substring so in the first case we will delete the character itself and call subproblem (i+1, j). In the second case we will iterate over all occurrence of the current character in right side, if K is the index of one such occurrence then the problem will reduce to two subproblems (i+1, K – 1) and (K+1, j). We can reach to this subproblem (i+1, K-1) because we can just delete the same character and call for mid substring. We need to take care of a case when first two characters are same in that case we can directly reduce to the subproblem (i+2, j)

So after above discussion of relation among subproblems, we can write dp relation as follows,

dp[i][j] = min(1 + dp[i+1][j],
          dp[i+1][K-1] + dp[K+1][j],  where s[i] == s[K]
          1 + dp[i+2][j] )
Total time complexity of above solution is O(n^3)

*/
class Solution {

    int[][] dp;

    public int minimumMoves(int[] arr) {
        dp = new int[arr.length][arr.length];
        return dfs(arr, 0, arr.length - 1);
    }

    private int dfs(int[] arr, int i, int j) {
        if (i >= j) {
            return i == j ? 1 : 0;
        }
        if (dp[i][j] > 0) {
            return dp[i][j];
        }

        int res = dfs(arr, i + 1, j) + 1;
        if (i + 1 < arr.length && arr[i] == arr[i + 1]) {
            res = Math.min(res, dfs(arr, i + 2, j) + 1);
        }

        for (int k = i + 2; k <= j; k++) {
            if (arr[i] == arr[k]) {
                res = Math.min(res, dfs(arr, i + 1, k - 1) + dfs(arr, k + 1, j));
            }
        }
        dp[i][j] = res;
        return res;
    }
}