class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null)
            return false;
        if (isSameTree(root, subRoot))
            return true;
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    private boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null || q == null)
            return p == q;
        return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

class Solution {
    public int subarraySum(int[] nums, int k) {
        int ans = 0, sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int target = sum - k;
            if (map.containsKey(target)) {
                ans += map.get(target);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }
}

class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int max = 0, sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0)
                nums[i] = -1;
            sum += nums[i];
            int target = sum;
            if (map.containsKey(target)) {
                max = Math.max(max, i - map.get(target));
            }
            map.putIfAbsent(sum, i);
        }
        return max;
    }
}

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (p.length() > s.length())
            return new ArrayList<>();
        List<Integer> ans = new ArrayList<>();
        int[] scount = new int[26];
        int[] pcount = new int[26];
        for (int i = 0; i < p.length(); i++) {
            pcount[p.charAt(i) - 'a'] += 1;
            scount[s.charAt(i) - 'a'] += 1;
        }
        for (int i = 0; i <= s.length() - p.length(); i++) {
            if (Arrays.equals(pcount, scount))
                ans.add(i);
            if (i != s.length() - p.length()) {
                scount[s.charAt(i) - 'a'] -= 1;
                scount[s.charAt(i + p.length()) - 'a'] += 1;
            }
        }
        return ans;
    }
}

class Solution {
    private final int[][] DIRECTIONS = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        boolean[][] reachPacific = new boolean[heights.length][heights[0].length];
        boolean[][] reachAtlantic = new boolean[heights.length][heights[0].length];
        for (int i = 0; i < heights.length; i++) {
            reachPacific[i][0] = true;
            reachAtlantic[i][heights[0].length - 1] = true;
        }

        for (int i = 0; i < heights[0].length; i++) {
            reachPacific[0][i] = true;
            reachAtlantic[heights.length - 1][i] = true;
        }

        for (int i = 0; i < heights[0].length; i++) {
            dfs(0, i, reachPacific, heights);
            dfs(heights.length - 1, i, reachAtlantic, heights);
        }
        for (int i = 0; i < heights.length; i++) {
            dfs(i, 0, reachPacific, heights);
            dfs(i, heights[0].length - 1, reachAtlantic, heights);
        }

        List<List<Integer>> ans = new ArrayList<>();
        for (int row = 0; row < heights.length; row++) {
            for (int col = 0; col < heights[0].length; col++) {
                if (reachPacific[row][col] && reachAtlantic[row][col]) {
                    ans.add(new ArrayList<>(Arrays.asList(row, col)));
                }
            }
        }
        return ans;
    }

    private void dfs(int row, int col, boolean[][] reach, int[][] heights) {
        for (int[] direction : DIRECTIONS) {
            int x = row + direction[0];
            int y = col + direction[1];
            if (!isOutOfBound(heights, x, y) && !reach[x][y] && heights[x][y] >= heights[row][col]) {
                reach[x][y] = true;
                dfs(x, y, reach, heights);
            }
        }
    }

    private boolean isOutOfBound(int[][] heights, int row, int col) {
        return row < 0 || row >= heights.length || col < 0 || col >= heights[0].length;
    }
}

class Solution {
    public boolean canPartition(int[] nums) {
        int totalSum = 0;
        // find sum of all array elements
        for (int num : nums) {
            totalSum += num;
        }
        // if totalSum is odd, it cannot be partitioned into equal sum subset
        if (totalSum % 2 != 0)
            return false;
        int subSetSum = totalSum / 2;
        int n = nums.length;
        Boolean[][] memo = new Boolean[n + 1][subSetSum + 1];
        // 关键是在这一行return. dfs的功能是判断从0到某个pos(不包括该pos)的范围内中的数字
        // 是否能够凑到给定的subSetSum. 但是问题是solution开始给传的
        // 是n - 1而不是n. 试了一下发现n也是可以的. 即使确实传的是的n - 1
        // 也就是判断从0到n - 1(刨去最后一个数字剩下的数字)能否凑成subSetSum.
        // 我们应该看的是两个dfs(num, n - 1, subSetSum, memo) 这个是不包含nums[n - 1]
        // 另一个是dfs(num, n - 1, subSetSum - nums[n - 1], memo)包含nums[n - 1]
        // 为何这里只写了第一种, 抛弃了第二种情况呢?
        // 关键在于如果能够凑成, 那么nums[n - 1]肯定属于其中的一个subset.
        // 我们假设它自己构成一个subset中的候选人, 还需要别的数字加入它来共同构成subSetSum
        // 于是我们在除了nums[n - 1]的其他数字中看一看是否能构成那另一个subset, 使得加一起等于subSetSum, 如果
        // 可以, 刨去这些构成这个另一个subSetSum的数字, 剩下的数字全部加入nums[n - 1]所在的阵营(subset)
        // 这样就可以了. 如果不行, 那么谁加入nums[n - 1]所在的subset都不管用. 因为假设某些数字加入刚好
        // 凑齐subSetSum, 那么我们在前n - 1个数字中是能够找到凑齐subSetSum的set的, 但根据我们的假设, 这样的
        // set是没有的, 于是和我们的假设冲突. 因此谁来和nums[n - 1]凑都不行.

        // 对于第一种:
        // 假设前从0到n - 1是可以凑成subSetSum的, 那么剩余的数字带上nums[n - 1]也可以凑成subSetNum
        // 假设是凑不成的, 那么数组中的数字谁来和nums[n - 1]也凑不成subSetSum.

        // 假设从0到n - 1是可以凑成subSetSum - nums[n - 1]的, 那么凑成的这些数字加上nums[n - 1]
        // 就凑成了subSetSum
        // 如果凑不成, 那么带上nums[n - 1]就更凑不成了.

        // 于是我们发现传入subSetSum和subSetSum - nums[n - 1]都可以.

        // 这一点儿也太让人费解了.
        return dfs(nums, n - 1, subSetSum - nums[n - 1], memo);
    }

    public boolean dfs(int[] nums, int n, int subSetSum, Boolean[][] memo) {
        // Base Cases
        if (subSetSum == 0)
            return true;
        if (n == 0 || subSetSum < 0)
            return false;
        // check if subSetSum for given n is already computed and stored in memo
        if (memo[n][subSetSum] != null)
            return memo[n][subSetSum];
        boolean result = dfs(nums, n - 1, subSetSum - nums[n - 1], memo) ||
                dfs(nums, n - 1, subSetSum, memo);
        // store the result in memo
        memo[n][subSetSum] = result;
        return result;
    }
}

class Solution {
    public String decodeString(String s) {
        return helper(s, 0, s.length() - 1);
    }

    private String helper(String s, int start, int end) {
        String ans = "";
        int pos = start;
        while (pos <= end) {
            char currChar = s.charAt(pos);
            if (!Character.isDigit(currChar)) {
                ans += currChar;
                pos += 1;
            } else {
                int digitEnd = pos;
                while (Character.isDigit(s.charAt(digitEnd))) {
                    digitEnd += 1;
                }
                int newStart = digitEnd + 1;
                int newEnd = findEnd(s, newStart);
                String newString = helper(s, newStart, newEnd - 2);
                int repeatingTimes = Integer.parseInt(s.substring(pos, digitEnd));
                for (int i = 0; i < repeatingTimes; i++) {
                    ans += newString;
                }
                pos = newEnd;
            }
        }
        return ans;
    }

    private int findEnd(String s, int start) {
        int pos = start;
        Stack<Character> leftBrackets = new Stack<>();
        leftBrackets.push('[');
        while (!leftBrackets.isEmpty()) {
            if (s.charAt(pos) == '[') {
                leftBrackets.push('[');
            } else if (s.charAt(pos) == ']') {
                leftBrackets.pop();
            }
            pos += 1;
        }
        return pos;
    }
}

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        for (int i = 1; i < ans.length; i++) {
            ans[i] = ans[i >> 1] + (i & 1);
        }
        return ans;
    }
}

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode oddHead = head, evenHead = head.next;
        ListNode ptrOne = head, prev = null;
        boolean isOdd = true;
        while (ptrOne.next != null) {
            ListNode next = ptrOne.next;
            ptrOne.next = next.next;
            prev = ptrOne;
            ptrOne = next;
            isOdd = !isOdd;
        }
        if (isOdd) {
            ptrOne.next = evenHead;
        } else {
            prev.next = evenHead;
        }
        return head;
    }
}

class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int max = -1, sum = 0;
        map.put(0, -1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int target = sum - k;
            // If there is a previous index which has the sume equals
            // to our target value.
            if (map.containsKey(target)) {
                max = Math.max(max, i - map.get(target));
            }
            // If have the same sum as a previous index then skip.
            // Only store current sum to map when there is no previous
            // index that has the same sum as the current index.
            map.putIfAbsent(sum, i);
        }
        return max == -1 ? 0 : max;

    }
}