LeetCode 401-500

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> result = new ArrayList<>();

        for (int hour = 0; hour < 12; hour++) {
            for (int minute = 0; minute < 60; minute++) {
                if (Integer.bitCount(hour) + Integer.bitCount(minute) == turnedOn) {
                    result.add(hour + (minute < 10 ? ":0" : ":") + minute);
                }
            }
        }

        return result;
    }
}

class Solution {
    public String removeKdigits(String num, int k) {
        int end = 0;
        char[] array = num.toCharArray();

        for (int i = 0; i < num.length(); i++) {
            // encounter a decreasing sequence, locate the digit to be overwritten
            while (end > 0 && k > 0 && array[end - 1] > array[i]) {
                k--;
                end--;
            }

            // skip leading '0' and overwrite one digit with a digit after
            if (end > 0 || array[i] != '0') {
                array[end] = array[i];
                end++;
            }
        }

        // if there are still k left, return 0 or truncate the last k digits
        return end <= k ? "0" : String.valueOf(array, 0, end - k);
    }
}

class Solution {
    // <index, set of all possible k>
    Map<Integer, Set<Integer>> checked = new HashMap<>();
    
    public boolean canCross(int[] stones) {
        for (int i = 0; i < stones.length; i++) {
            checked.put(stones[i], new HashSet<>());
        }
        return helper(0, 1, stones[stones.length - 1]);
    }

    private boolean helper(int current, int k, int last) {
        if (current == last) {
            return true;
        }
        
        // skip if we have checked this k at the current stone
        if (k <= 0 || checked.get(current).contains(k)) {
            return false;
        }
        
        int next = current + k;
        if (checked.containsKey(next)) {
            if (helper(next, k - 1, last) || helper(next, k, last) || helper(next, k + 1, last)) {
                return true;
            }
        }
        checked.get(current).add(k);
        
        return false;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        int result = 0;
        
        if (root == null) {
            return result;
        }
        
        if (root.left != null) {
            if (root.left.left == null && root.left.right == null) {
                result += root.left.val;
            } else {
                result += sumOfLeftLeaves(root.left);
            }
        }

        if (root.right != null) {
            result += sumOfLeftLeaves(root.right);
        }
        
        return result;
    }
}

class Solution {
    public String toHex(int num) {
        if (num == 0) {
            return "0";
        }

        char[] map = new char[] {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
        StringBuilder sb = new StringBuilder();
        while (num != 0) {
            // transform last 4 bits to hex
            sb.append(map[num & 15]);
            
            // get rid of the last 4 bits
            num >>>= 4;
        }
        
        return sb.reverse().toString();
    }
}

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (a, b) -> (a[0] == b[0] ? a[1] - b[1] : b[0] - a[0]));

        List<int[]> result = new LinkedList<>();
        for (int[] p : people) {
            result.add(p[1], p);
        }

        return result.toArray(new int[result.size()][]);
    }
}

class Solution {
    private int water = 0;    
    private boolean[][] visited;
    private int visitedCnt = 0;

    private static class Block implements Comparable<Block> {
        int row;
        int col;
        int value;
        
        Block(int row, int col, int value) {
            this.row = row;
            this.col = col;
            this.value = value;
        }
        
        @Override
        public int compareTo(Block block) {
            return value - block.value;
        }
    }

    public int trapRainWater(int[][] heightMap) {
        if (heightMap == null || heightMap.length < 3 || heightMap[0].length < 3) {
            return 0;
        }

        int rows = heightMap.length;
        int cols = heightMap[0].length;
        PriorityQueue<Block> pq = new PriorityQueue<Block>();
        visited = new boolean[rows][cols];

        // add row edge blocks to priority queue
        for (int i = 0; i < cols; i++) {
            Block block1 = new Block(0, i, heightMap[0][i]);
            Block block2 = new Block(rows - 1, i, heightMap[rows - 1][i]);
            pq.offer(block1);
            pq.offer(block2);
            visited[0][i] = true;
            visited[rows - 1][i] = true;
            visitedCnt += 2;
        }

        // add column edge blocks to priority queue
        for (int i = 1; i < rows - 1; i++) {
            Block block1 = new Block(i, 0, heightMap[i][0]);
            Block block2 = new Block(i, cols - 1, heightMap[i][cols - 1]);
            pq.offer(block1);
            pq.offer(block2);
            visited[i][0] = true;
            visited[i][cols - 1] = true;
            visitedCnt += 2;
        }

        // BFS
        while (visitedCnt < rows * cols) {
            Block block = pq.poll();
            fill(block.row - 1, block.col, block.value, pq, heightMap);
            fill(block.row, block.col - 1, block.value, pq, heightMap);
            fill(block.row + 1, block.col, block.value, pq, heightMap);
            fill(block.row, block.col + 1, block.value, pq, heightMap);
        }
        
        return water;
    }


    public void fill(int row, int col, int min, PriorityQueue<Block> pq, int[][] heightMap) {
        if (row < 0 || col < 0 || row >= heightMap.length || col >= heightMap[0].length || visited[row][col]) {
            // out of bound, or visited block
            return;
        } else if (heightMap[row][col] >= min) {
            // visit a higher block, add to queue and mark it as visited
            Block newBlock = new Block(row, col, heightMap[row][col]);
            pq.offer(newBlock);
            visited[row][col] = true;
            visitedCnt++;
        } else {
            // visit a lower block, add water to be trapped
            water += min - heightMap[row][col];
            visited[row][col] = true;
            visitedCnt++;
            fill(row - 1, col, min, pq, heightMap);
            fill(row, col - 1, min, pq, heightMap);
            fill(row + 1, col, min, pq, heightMap);
            fill(row, col + 1, min, pq, heightMap);
        }
    }
}

class Solution {
    public boolean validWordAbbreviation(String word, String abbr) {
        int number = 0;
        int i = 0, j = 0;

        while (i < word.length() && j < abbr.length()) {
            if (abbr.charAt(j) >= '0' && abbr.charAt(j) <= '9') {
                number = number * 10 + abbr.charAt(j) - '0';
                if (number == 0) {
                    return false;
                }
                j++;
            } else {
                i += number;
                if (i >= word.length() || word.charAt(i) != abbr.charAt(j)) {
                    return false;
                }
                number = 0;
                i++;
                j++;
            }
        }

        // abbr ends with number
        i += number; 
        return i == word.length() && j == abbr.length();
    }
}

class Solution {
    public int longestPalindrome(String s) {
        int[] freq = new int[128];
        for (int i = 0; i < s.length(); i++) {
            freq[s.charAt(i)]++;
        }

        int odd = 0;
        for (int i = 0; i < freq.length; i++) {
            if (freq[i] % 2 != 0) {
                odd++;
            }
        }
            
        return odd < 2 ? s.length() : s.length() - odd + 1;
    }
}

class Solution {
    public int splitArray(int[] nums, int m) {
        int minVal = Integer.MIN_VALUE, maxVal = 0;
        for (int num : nums) {
            minVal = Math.max(minVal, num);
            maxVal += num;
        }

        while (minVal < maxVal) {
            int mid = minVal + (maxVal - minVal) / 2;
            
            if (canSplit(mid, nums, m)) {
                maxVal = mid;
            } else {
                minVal = mid + 1;
            }
        }

        return minVal;
    }

    private boolean canSplit(int upperBoundSubarraySum, int[] nums, int m) {
        int curSubarraySum = 0, subarrayCount = 1;
        
        for (int num : nums) {
            curSubarraySum += num;
            
            if (curSubarraySum > upperBoundSubarraySum) {
                subarrayCount++;
                curSubarraySum = num;
                if (subarrayCount > m) {
                    return false;
                }
            }
        }

        return true;
    }
}

class Solution {
    public String minAbbreviation(String target, String[] dic) {
        Set<Integer> diffs = new HashSet<>();
        int targetLen = target.length();

        for (String word : dic) {
            if (word.length() == targetLen) {
                // mark each bit's difference between target and word
                int diff = 0;
                for (int i = 0; i < targetLen; i++) {
                    if (target.charAt(i) != word.charAt(i))  {
                        diff += 1 << i;
                    }
                }
                        
                diffs.add(diff);
            }
        }

        // all words have different length, then return the shortest abbr
        if (diffs.isEmpty()) {
            return Integer.toString(targetLen);
        }

        int bits = Integer.MIN_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < (1 << targetLen); i++) {
            boolean flag = true;

            // skip cases that are totally different from dic
            for (int diff : diffs) {
                if ((i & diff) == 0) {
                    flag = false;
                    break;
                }
            }

            // get maximum conflicting bits
            if (flag) {
                int sum = 0;
                for (int j = 0; j < targetLen - 1; j++) {
                    if (((i >> j) & 3) == 0) {
                        sum++;
                    }
                }
                    
                if (sum > max) {
                    max = sum;
                    bits = i;
                }
            }
        }

        StringBuilder result = new StringBuilder();
        int count = 0;
        for (int i = 0; i < targetLen; i++) {

            // current pos cannot be replaced with an abbr digit, must use alphabet instead
            if ((bits & (1 << i)) != 0) {
                if (count != 0) {
                    result.append(count);
                    count = 0;
                }
                result.append(target.charAt(i));
            } else {
                count++;
            }
        }

        if (count != 0) {
            result.append(count);
        }
        return result.toString();
    }
}

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> result = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0 && i % 5 == 0) {
                result.add("FizzBuzz");
            } else if (i % 3 == 0) {
                result.add("Fizz");
            } else if (i % 5 == 0) {
                result.add("Buzz");
            } else {
                result.add(String.valueOf(i));
            }
        }
        
        return result;
    }
}

class Solution {
    public List<String> fizzBuzz(int n) {
        // define the order of how you want to concat the words here using lambda comparator
        TreeMap<Integer, String> map = new TreeMap<>((a, b) -> a - b); 
        map.put(3, "Fizz");
        map.put(5, "Buzz");
        // map.put(7, "Yuzz"); 
        // map.put(9, "Mozz");
        // add more encoding options here ... 
        
        List<String> result = new LinkedList();
        for (int i = 1; i <= n; i++) { 
            StringBuilder encoded = new StringBuilder();
            for (int num : map.keySet()) {
                if (i % num == 0) {
                    encoded.append(map.get(num));
                }
            }
            
            result.add((encoded.length() == 0) ? String.valueOf(i) : encoded.toString());
        }
        
        return result;
    }
}

class Solution {
    public int numberOfArithmeticSlices(int[] A) {
        int newSlice = 0, result = 0;
        
        for (int i = 2; i < A.length; i++) {
            if (A[i-1] - A[i-2] == A[i] - A[i-1]) {
                newSlice++;
                result += newSlice;
            } else {
                newSlice = 0;
            }
        }
        
        return result;
    }
}

class Solution {
    public int thirdMax(int[] nums) {
        Integer max1 = null;
        Integer max2 = null;
        Integer max3 = null;

        for (Integer n : nums) {
            if (n.equals(max1) || n.equals(max2) || n.equals(max3)) {
                continue;
            }
            
            if (max1 == null || n > max1) {
                max3 = max2;
                max2 = max1;
                max1 = n;
            } else if (max2 == null || n > max2) {
                max3 = max2;
                max2 = n;
            } else if (max3 == null || n > max3) {
                max3 = n;
            }
        }
        
        return max3 == null ? max1 : max3;
    }
}

class Solution {
    public int thirdMax(int[] nums) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        Set<Integer> set = new HashSet<>();
        
        for (int n : nums) {
            if (set.add(n)) {
                pq.offer(n);
                
                if (pq.size() > 3) {
                    pq.poll();
                }
            }
        }
        
        if (pq.size() == 2) {
            pq.poll();
        }
        return pq.peek();
    }
}

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder result = new StringBuilder();
        int carry = 0;
        int len1 = num1.length() - 1;
        int len2 = num2.length() - 1;

        while (len1 >= 0 || len2 >= 0) {
            int x = len1 >= 0 ? num1.charAt(len1) - '0' : 0;
            int y = len2 >= 0 ? num2.charAt(len2) - '0' : 0;
            int sum = (x + y + carry) % 10;
            carry = (x + y + carry) / 10;
            result.append(sum);
            len1--;
            len2--;
        }

        if (carry != 0) {
            result.append(carry);
        }
        return result.reverse().toString();
    }
}

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int val: nums) sum += val;
        if (sum % 2 == 1) {
            return false;
        }
        sum /= 2;

        Boolean[] dp = new Boolean[sum + 1];
        dp[0] = true;
        boolean result = canPartition(sum, 0, nums, dp);
        return result;
    }

    private boolean canPartition(int sum, int pos, int[] nums, Boolean[] dp) {
        if (sum == 0) {
            return true;
        }
        if (sum < 0 || pos == nums.length) {
            return false;
        }
        if (dp[sum] != null) {
            return dp[sum];
        }

        dp[sum] = canPartition(sum - nums[pos], pos + 1, nums, dp) || canPartition(sum, pos + 1, nums, dp);
        return dp[sum];
    }
}

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> result = new ArrayList<>();
        if (matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];

        // top and bottom
        for (int col = 0; col < n; col++) {
            dfs(matrix, 0, col, matrix[0][col], pacific);
            dfs(matrix, m-1, col, matrix[m-1][col], atlantic);
        }

        // left and right
        for (int row = 0; row < m; row++) {
            dfs(matrix, row, 0, matrix[row][0], pacific);
            dfs(matrix, row, n-1, matrix[row][n-1], atlantic);
        }

        // find all grids that meet requirements
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    List<Integer> temp = new ArrayList();
                    temp.add(i);
                    temp.add(j);
                    result.add(temp);
                }
            }
        }
        
        return result;
    }

    private void dfs(int[][] matrix, int r, int c, int preHeight, boolean[][] ocean) {
        // skip out-of-bound & higher flow & visited cases
        if (r < 0 || c < 0 || r > matrix.length-1 || c > matrix[0].length-1 || matrix[r][c] < preHeight || ocean[r][c]) {
            return;
        }

        ocean[r][c] = true;
        dfs(matrix, r - 1, c, matrix[r][c], ocean); // up
        dfs(matrix, r + 1, c, matrix[r][c], ocean); // down
        dfs(matrix, r, c - 1, matrix[r][c], ocean); // left
        dfs(matrix, r, c + 1, matrix[r][c], ocean); // right
    }
}

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        // a new line which is starting with certain index in sentence, what is the starting index of next line
        int[] nextIndex = new int[sentence.length];

        // how many times the pointer in current line passes over the last index
        int[] times = new int[sentence.length];

        for (int i = 0; i < sentence.length; i++) {
            int curLen = 0;
            int cur = i;
            int time = 0;

            while (curLen + sentence[cur].length() <= cols) {
                // word + space
                curLen += sentence[cur].length() + 1;
                cur++;

                // the whole sentence is added for a time
                if (cur == sentence.length) {
                    cur = 0;
                    time++;
                }
            }

            // stop at the first word of next line and times of the previous line
            nextIndex[i] = cur;
            times[i] = time;
        }

        int result = 0;
        int cur = 0; // start from the first word in the sentence
        for (int i = 0; i < rows; i++) {
            result += times[cur]; 
            cur = nextIndex[cur]; // update start of next row
        }
        
        return result;
    }
}

class Solution {
    public int countBattleships(char[][] board) {
        if (board.length == 0 || board[0].length == 0) {
            return 0;
        }

        int result = 0;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == '.') {
                    continue;
                }

                // 1 x N or N x 1, thus we can always check left or up grid to determine the same battleship
                if ((i > 0 && board[i-1][j] == 'X') || (j > 0 && board[i][j-1] == 'X')) {
                    continue;
                }
                result++;
            }
        }

        return result;
    }
}

class Solution {
    public int strongPasswordChecker(String s) {
        int result = 0;
        
        // number of missing lowercase letters, uppercase letters and digits
        int a = 1, A = 1, d = 1;
        
        // number of repeating characters starting at the corresponding position in the string
        char[] carr = s.toCharArray();
        int[] arr = new int[carr.length];

        for (int i = 0; i < arr.length;) {
            char currentChar = carr[i];
            if (Character.isLowerCase(currentChar)) a = 0;
            if (Character.isUpperCase(currentChar)) A = 0;
            if (Character.isDigit(currentChar)) d = 0;

            int j = i;
            while (i < carr.length && carr[i] == carr[j]) {
                i++;
            }
            arr[j] = i - j;
        }

        int totalMissing = (a + A + d);

        // pad length to at least 6
        if (arr.length < 6) {
            result += totalMissing + Math.max(0, 6 - (arr.length + totalMissing));
        } else {
            int overLenCharNum = Math.max(arr.length - 20, 0), leftOverNum = 0;
            result += overLenCharNum;

            for (int k = 1; k < 3; k++) {
                for (int i = 0; i < arr.length && overLenCharNum > 0; i++) {
                    if (arr[i] < 3 || arr[i] % 3 != (k - 1)) {
                        continue;
                    }

                    // turn all numbers in the arr array greater than 2 into the form of (3m + 2)
                    arr[i] -= Math.min(overLenCharNum, k);
                    overLenCharNum -= k;
                }
            }

            for (int i = 0; i < arr.length; i++) {
                if (arr[i] >= 3 && overLenCharNum > 0) {
                    // minimum number of changes needed to fix the repeating character problem by deletion only
                    int need = arr[i] - 2;
                    arr[i] -= overLenCharNum;
                    overLenCharNum -= need;
                }

                if (arr[i] >= 3) {
                    leftOverNum += arr[i] / 3;
                }
            }

            result += Math.max(totalMissing, leftOverNum);
        }

        return result;
    }
}

class Solution {
    public int findMaximumXOR(int[] nums) {
        int max = 0, mask = 0;

        // find max number to get max length
        int maxNum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            maxNum = Math.max(maxNum, nums[i]);
        }
            
        int len = Integer.toBinaryString(maxNum).length(); 

        for (int i = len - 1; i >= 0; i--) {
            // The mask will grow like  100..000 , 110..000, 111..000,  then 1111...111
            mask = mask | (1 << i);

            HashSet<Integer> set = new HashSet<>();

            // only care about the left parts
            for (int num : nums) {
                set.add(num & mask);
            }

            // try to find a candidate which can give the greediest try;
            int tmp = max | (1 << i);
            for (int prefix : set) {
                // if a ^ b = c, then a ^ c = b
                // to get b, we need a ^ c, if a ^ c exisited in our set, then we're good to go
                if (set.contains(tmp ^ prefix)) {
                    max = tmp;
                    break;
                }
            }
        }
        
        return max;
    }
}

class Solution {
    public boolean validWordSquare(List<String> words) {
        if (words == null || words.isEmpty()) {
            return false;
        }
        int m = words.size();
        char[][] matrix = new char[m][m];

        for (int i = 0; i < m; i++) {
            String word = words.get(i);
            if (word.length() > m) {
                return false;
            }
            System.arraycopy(word.toCharArray(), 0, matrix[i], 0, word.length());
        }

        for (int row = 0; row < m; row++) {
            for (int col = row; col < m; col++) {
                if (matrix[row][col] != matrix[col][row]) {
                    return false;
                }     
            }
        }
        return true;
    }
}

class Solution {
    public String originalDigits(String s) {
        // hashmap, map letter into its frequency
        char[] count = new char[26 + (int)'a'];
        for (char letter: s.toCharArray()) {
            count[letter]++;
        }

        // map array, map digit into its frequency
        int[] out = new int[10];

        // letter "z" only in "zero"
        out[0] = count['z'];

        // letter "w" only in "two"
        out[2] = count['w'];

        // letter "u" only in "four"
        out[4] = count['u'];

        // letter "x" only in "six"
        out[6] = count['x'];

        // letter "g" only in "eight"
        out[8] = count['g'];

        // letter "h" only in "three" and "eight"
        out[3] = count['h'] - out[8];

        // letter "f" only in "five" and "four"
        out[5] = count['f'] - out[4];

        // letter "s" only in "seven" and "six"
        out[7] = count['s'] - out[6];

        // letter "i" is in "nine", "five", "six", and "eight"
        out[9] = count['i'] - out[5] - out[6] - out[8];

        // letter "n" is in "one", "nine", and "seven"
        out[1] = count['n'] - out[7] - 2 * out[9];

        StringBuilder result = new StringBuilder();
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < out[i]; j++) {
                result.append(i);
            }
        }
        return result.toString();
    }
}

class Solution {
    public int characterReplacement(String s, int k) {
        int maxCount = 0; // largest count of a single, unique character in the current window
        int maxLength = 0;
        int[] freq = new int[26];

        char[] chars = s.toCharArray();
        for (int start = 0, end = 0; end < s.length(); end++) {
            maxCount = Math.max(maxCount, ++freq[chars[end] - 'A']);

            // at most k replacements in the window, and there are more characters in the window than we can replace
            if (end - start + 1 - maxCount > k) {
                freq[chars[start] - 'A']--;
                start++;
            }
            
            maxLength = Math.max(maxLength, end - start + 1);
        }

        return maxLength;
    }
}

class Solution {
    class TrieNode {
        List<String> list; // all words that have this node as prefix
        TrieNode[] children;
        TrieNode() {
            list = new ArrayList<>();
            children = new TrieNode[26];
        }
    }

    // O(n^len) * len
    public List<List<String>> wordSquares(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            root.list.add(w);
            TrieNode tn = root;

            for (char ch : w.toCharArray()) {
                if (tn.children[ch - 'a'] == null) {
                    tn.children[ch - 'a'] = new TrieNode();
                }
                tn = tn.children[ch - 'a'];

                // add word to each node in the tree
                tn.list.add(w);
            }
        }

        // length of square
        int len = words[0].length();

        // form n tries starting from root, one trie for each word
        // tns[i] tells us in the DFS, for word[i], which letter is available next
        TrieNode[] tns = new TrieNode[len];
        Arrays.fill(tns, root);

        List<List<String>> result = new ArrayList<>();
        dfs(0, new char[len][len], result, tns);
        return result;
    }

    private void dfs(int idx, char[][] m, List<List<String>> result, TrieNode[] tns) {
        // one word square, add all the strings to result
        if (idx == m.length) {
            List<String> wordSquare = new ArrayList<>(idx);
            for (char[] ca : m) {
                wordSquare.add(new String(ca));
            }
            result.add(wordSquare);
            return;
        }

        TrieNode[] tns2 = new TrieNode[tns.length];

        //for each word in prefix list of this idx node, recursively build the word square starting from cand
        for (String cand : tns[idx].list) {
            int i = idx;

            // set m[idx][i] to be cand[idx] the first time in this for loop
            // for every after iteration i, set m[idx][i] and m[i][idx] to be cand[idx+i]
            // check if one of the tns2 possible roots contain that ch, otherwise backtrack from dfs to try another candidate word
            for (; i < m.length; ++i) {
                char ch = cand.charAt(i);
                m[idx][i] = ch; 
                if (i > idx) {
                    if (tns[i].children[ch - 'a'] == null) {
                        break;
                    }
                    m[i][idx] = ch;            

                    //tns2 serves as the trie node for each position i that we are trying to fill
                    tns2[i] = tns[i].children[ch - 'a']; 
                }
            }

            // found a match for every letter in this cand word, then dfs at next level
            if (i == m.length) {
                dfs(idx + 1, m, result, tns2); 
            }
        }
    }    
}

class Solution {
    Node curr = null;
    
    public Node treeToDoublyList(Node root) {
        if (root == null) {
            return root;
        }

        Node dummyHead = new Node(0);
        curr = dummyHead;

        // inorder tranversal by recursion to connect the original BST
        inOrderConnect(root);

        // connect head and tail, notice that current ptr is tail
        curr.right = dummyHead.right;
        dummyHead.right.left = curr;

        return dummyHead.right;
    }

    private void inOrderConnect(Node node) {
        if (node == null) {
            return;
        }

        inOrderConnect(node.left);

        // construct doubly link
        curr.right = node;
        node.left = curr;
        curr = node;

        inOrderConnect(node.right);
    }
}

/*
// Definition for a QuadTree node.
class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;

    
    public Node() {
        this.val = false;
        this.isLeaf = false;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = null;
        this.topRight = null;
        this.bottomLeft = null;
        this.bottomRight = null;
    }
    
    public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
        this.val = val;
        this.isLeaf = isLeaf;
        this.topLeft = topLeft;
        this.topRight = topRight;
        this.bottomLeft = bottomLeft;
        this.bottomRight = bottomRight;
    }
};
*/

class Solution {
    public Node construct(int[][] grid) {
        return helper(grid, 0, 0, grid.length);
    }

    private Node helper(int[][] grid, int x, int y, int len) {
        // the minimum grid
        if (len == 1) {
            return new Node(grid[x][y] != 0, true);
        }

        Node result = new Node();
        Node topLeft = helper(grid, x, y, len / 2);
        Node topRight = helper(grid, x, y + len / 2, len / 2);
        Node bottomLeft = helper(grid, x + len / 2, y, len / 2);
        Node bottomRight = helper(grid, x + len / 2, y + len / 2, len / 2);

        
        if (topLeft.isLeaf && topRight.isLeaf && bottomLeft.isLeaf && bottomRight.isLeaf
            && topLeft.val == topRight.val && topRight.val == bottomLeft.val && bottomLeft.val == bottomRight.val) {
            // current grid has the same value
            result.isLeaf = true;
            result.val = topLeft.val;
        } else {
            // up to parent node
            result.topLeft = topLeft;
            result.topRight = topRight;
            result.bottomLeft = bottomLeft;
            result.bottomRight = bottomRight;
        }
        
        return result;
    }
}

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Codec {
    // Encodes a tree to a single string.
    public String serialize(Node root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    private void serialize(Node node, StringBuilder sb) {
        if (node == null) {
            return;
        }

        // append value char
        sb.append((char) (node.val + '0'));
        
        // append children size char
        sb.append((char) (node.children.size() + '0'));

        for (Node n : node.children) {
            serialize(n, sb);
        }
    }

    // Decodes your encoded data to tree.
    public Node deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        return deserialize(data, new int[1]);
    }

    Node deserialize(String data, int[] index) {
        int val = data.charAt(index[0]) - '0';
        int childrenSize = data.charAt(++index[0]) - '0';

        Node node = new Node(val, new ArrayList<Node>());
        for (int i = 0; i < childrenSize; i++) {
            index[0]++;
            node.children.add(deserialize(data, index));
        }
        
        return node;
    }
}

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List< List<Integer> > result = new ArrayList<>();
        if (root == null) {
            return result;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            List<Integer> curLevel = new ArrayList<>();

            // these are all nodes in current level
            int currentLevelSize = queue.size();
            for (int i = 0; i < currentLevelSize; i++) {
                Node cur = queue.poll();
                curLevel.add(cur.val);

                // add current node's children to queue
                for (Node child : cur.children) {
                    queue.offer(child);
                }
            }

            // finish a level, add current level's value to result
            result.add(curLevel);
        }

        return result;
    }
}

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

class Solution {
    public Node flatten(Node head) {
        if (head == null) {
            return null;
        }

        Node dummyHead = new Node(0, null, head, null);
        Node cur, prev = dummyHead;

        // set a stack and push head into it
        Stack<Node> stack = new Stack();
        stack.push(head);

        while (!stack.isEmpty()) {
            cur = stack.pop();

            // link previous and current node
            prev.next = cur;
            cur.prev = prev;

            // push next node or child node
            if (cur.next != null) stack.push(cur.next);
            if (cur.child != null) {
                stack.push(cur.child);

                // unlink current node with child
                cur.child = null;
            }

            // move pointers forward
            prev = cur;
        }

        // link first node with dummyHead to make a valid doubly linked list
        dummyHead.next.prev = null;

        return dummyHead.next;
    }
}

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Codec {
    // Encodes an n-ary tree to a binary tree.
    public TreeNode encode(Node root) {
        if (root == null) {
            return null;
        }
        TreeNode result = new TreeNode(root.val);

        // next level -> left
        if (root.children.size() > 0) {
            result.left = encode(root.children.get(0));
        }

        // same level -> right
        TreeNode cur = result.left;
        for (int i = 1; i < root.children.size(); i++) {
            cur.right = encode(root.children.get(i));
            cur = cur.right;
        }
        return result;
    }
	
    // Decodes your binary tree to an n-ary tree.
    public Node decode(TreeNode root) {
        if (root == null) {
            return null;
        }
        Node result = new Node(root.val, new ArrayList<>());

        // first child is root.left, all other children are on the right subtree
        TreeNode cur = root.left;
        while (cur != null) {
            result.children.add(decode(cur));
            cur = cur.right;
        }

        return result;
    }
}

class AllOne {

    Map<String, Node> map;
    Node head, tail;
    
    class Node {
        int val;
        LinkedHashSet<String> keys;
        Node next, pre;
        public Node(int val) {
            this.val = val;
            keys = new LinkedHashSet();
            next = pre = null;
        }
    }

    /** Initialize your data structure here. */
    public AllOne() {
        map = new HashMap();
        head = tail = null;
    }
    
    /** Inserts a new key <Key> with value 1. Or increments an existing key by 1. */
    public void inc(String key) {
        if (map.containsKey(key)) {
            // get old node
            Node node = map.get(key);
            int val = node.val;
            
            // remove old key in the old node
            node.keys.remove(key);
            
            // add new node with new val
            if (node.next == null || node.next.val != val + 1) {
                Node newNode = new Node(val + 1);
                newNode.pre = node;
                newNode.next = node.next;
                node.next = newNode;
                if (newNode.next != null) {
                    newNode.next.pre = newNode;
                }
            }
            
            // add new key to the next node
            node.next.keys.add(key);
            
            // update node
            map.put(key, node.next);
            
            // update head
            if (node.keys.isEmpty()) {
                if (node == head) {
                    head = node.next;
                }
                node.next.pre = node.pre;
                if (node.pre != null) {
                    node.pre.next = node.next;
                }
            }
            
            // update tail
            if (tail == node) {
                tail = node.next;
            }
        } else {
            if (head == null || head.val > 1) {
                Node node = new Node(1);
                node.next = head;
                if (head != null) {
                    head.pre = node;
                }
                head = node;
                if (tail == null) {
                    tail = node;
                }
            }
            head.keys.add(key);
            map.put(key, head);
        }
    }
    
    /** Decrements an existing key by 1. If Key's value is 1, remove it from the data structure. */
    public void dec(String key) {
        if (!map.containsKey(key)) {
            return;
        }
        
        // get old node
        Node node = map.get(key);
        int val = node.val;
        
        // remove old val from old node
        node.keys.remove(key);
        
        // remove old key from map
        map.remove(key);
        
        // if it's head, update head and tail
        if (val == 1) {
            if (node.keys.isEmpty()) {
                if (head == node) {
                    head = node.next;
                }
                if (head != null) {
                    head.pre = null;
                }
                if (tail == node) {
                    tail = null;
                }
            }
        } else {
            // add new node at pre position
            if (node.pre == null || node.pre.val != val - 1) {
                Node newNode = new Node(val - 1);
                newNode.next = node;
                newNode.pre = node.pre;
                node.pre = newNode;
                if (newNode.pre != null) {
                    newNode.pre.next = newNode;
                }
            }
            
            // add new key to the newNode or pre node
            node.pre.keys.add(key);
            
            // update node
            map.put(key, node.pre);
            
            // update tail
            if (node.keys.isEmpty()) {
                if (tail == node) {
                    tail = node.pre;
                }
                node.pre.next = node.next;
                if (node.next != null) {
                    node.next.pre = node.pre;
                }
            }
            
            // update head
            if (head == node) {
                head = node.pre;
            }
        }
    }
    
    /** Returns one of the keys with maximal value. */
    public String getMaxKey() {
        return tail == null ? "" : tail.keys.iterator().next();
    }
    
    /** Returns one of the keys with Minimal value. */
    public String getMinKey() {
        return head == null ? "" : head.keys.iterator().next();
    }
}

/**
 * Your AllOne object will be instantiated and called as such:
 * AllOne obj = new AllOne();
 * obj.inc(key);
 * obj.dec(key);
 * String param_3 = obj.getMaxKey();
 * String param_4 = obj.getMinKey();
 */

class Solution {
    private int count = Integer.MAX_VALUE;
    
    public int minMutation(String start, String end, String[] bank) {
        recurse(start, end, bank, 0, new HashSet<String>());
        return count == Integer.MAX_VALUE ? -1 : count;
    }

    private void recurse(String start, String end, String[] bank, int mutateNum, Set<String> visited) {
        if (start.equals(end)) {
            count = Math.min(count, mutateNum);
        }

        for (String e : bank) {
            int diff = 0;
            
            // only 1 diff is allowed to mutate to the next state
            for (int i = 0; i < e.length(); i++) {
                if (start.charAt(i) != e.charAt(i)) {
                    diff++;
                    if (diff > 1) {
                        break;
                    }
                }
            }

            // backtrack, try to mutate to next state then come back
            if (diff == 1 && !visited.contains(e)) {
                visited.add(e);
                recurse(e, end, bank, mutateNum + 1, visited);
                visited.remove(e);
            }
        }
    }
}

class Solution {
    public int countSegments(String s) {
        s = s.trim();
        if (s == null || s.length() == 0) {
            return 0;
        }

        String[] result = s.split("\\s+");
        return result.length;
    }
}

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals == null || intervals.length == 0 || intervals[0].length == 0) {
            return 0;
        }

        // sort by end element
        Arrays.sort(intervals, (int[] a, int[] b) -> { return a[1] - b[1]; });

        int end = intervals[0][1];
        int nonOverlap = 1;        

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= end) {
                end = intervals[i][1];
                nonOverlap++;
            }
        }
        
        return intervals.length - nonOverlap;
    }
}

class Solution {
    public int[] findRightInterval(int[][] intervals) {
        if (intervals == null || intervals.length == 0 || intervals[0].length == 0) {
            return new int[] {};
        }

        int[] result = new int[intervals.length];

        // find min start and max end
        int min = intervals[0][0], max = intervals[0][1];
        for (int i = 1 ; i < intervals.length; i++) {
            min = Math.min(min, intervals[i][0]);
            max = Math.max(max, intervals[i][1]);
        }

        int[] buckets = new int[max - min + 1];
        Arrays.fill(buckets, -1);
        for (int i = 0; i < intervals.length; i++) {
            buckets[intervals[i][0] - min] = i;
        }

        for (int i = buckets.length - 2; i >= 0; i--) {
            if (buckets[i] == -1) {
                buckets[i] = buckets[i+1]; 
            }
        }   

        for (int i = 0; i < intervals.length; i++) {
            result[i] = buckets[intervals[i][1] - min];
        }

        return result;
    }
}