class Solution {
    public int longestValidParentheses(String s) {
        int left = 0, right = 0, max = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                left += 1;
            } else {
                right += 1;
            }
            if (left == right) {
                max = Math.max(max, left * 2);
            } else if (left < right) {
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == '(') {
                left += 1;
            } else {
                right += 1;
            }
            if (left == right) {
                max = Math.max(max, left * 2);
            } else if (left > right) {
                left = right = 0;
            }
        }
        return max;
    }
}

class Solution {
    private int ans = 0;

    public int longestConsecutive(TreeNode root) {
        helper(root);
        return ans;
    }

    private int helper(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int leftTreeStreak = helper(node.left);
        int rightTreeStreak = helper(node.right);
        int currStreak = 1;
        if (node.left != null && node.val + 1 == node.left.val) {
            currStreak = Math.max(currStreak, leftTreeStreak + 1);
        }
        if (node.right != null && node.val + 1 == node.right.val) {
            currStreak = Math.max(currStreak, rightTreeStreak + 1);
        }
        ans = Math.max(ans, currStreak);
        return currStreak;
    }
}

class Solution {
    public String reverseWords(String s) {
        Deque<String> words = new ArrayDeque<>();
        for (String substring : s.split(" ")) {
            if (substring.length() == 0) {
                continue;
            }
            words.offerLast(new StringBuilder(substring).toString());
        }
        if (words.isEmpty()) {
            return "";
        }
        StringBuilder ans = new StringBuilder();
        while (!words.isEmpty()) {
            ans.append(words.pollLast())
                    .append(" ");
        }
        ans.deleteCharAt(ans.length() - 1);
        return ans.toString();
    }
}

class Solution {
    private int ans;

    public int sumNumbers(TreeNode root) {
        int ans = 0;
        Deque<Pair<TreeNode, Integer>> stack = new ArrayDeque<>();
        stack.push(new Pair(root, 0));
        while (!stack.isEmpty()) {
            Pair<TreeNode, Integer> currPair = stack.pop();
            TreeNode currNode = currPair.getKey();
            int currNum = currPair.getValue();
            if (currNode != null) {
                currNum = currNum * 10 + currNode.val;
                if (currNode.left == null && currNode.right == null) {
                    ans += currNum;
                } else {
                    stack.push(new Pair(currNode.left, currNum));
                    stack.push(new Pair(currNode.right, currNum));
                }
            }
        }
        return ans;
    }
}

class Solution {
    private int ans;

    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    private void dfs(TreeNode node, int numAbove) {
        if (node == null) {
            return;
        }
        int currNum = numAbove * 10 + node.val;
        if (node.left == null && node.right == null) {
            ans += currNum;
            return;
        }
        dfs(node.left, currNum);
        dfs(node.right, currNum);
    }
}

class Solution {
    public String simplifyPath(String path) {
        // letter or _ | . | /
        Deque<String> deque = new ArrayDeque<>();
        int ptr = 0;
        while (ptr < path.length()) {
            while (ptr < path.length() && path.charAt(ptr) == '/') {
                ptr += 1;
            }
            if (ptr == path.length()) {
                break;
            }
            StringBuilder currSub = new StringBuilder();
            while (ptr < path.length() && path.charAt(ptr) != '/') {
                currSub.append(path.charAt(ptr));
                ptr += 1;
            }
            String s = currSub.toString();
            if (s.equals("..")) {
                if (!deque.isEmpty()) {
                    deque.pollLast();
                }
            } else if (!s.equals(".")) {
                deque.offerLast(s);
            }
        }
        StringBuilder ans = new StringBuilder();
        while (!deque.isEmpty()) {
            ans.append("/").append(deque.pollFirst());
        }
        return ans.length() == 0 ? "/" : ans.toString();
    }
}

class Solution {
    private int modulo = 1000000007;
    private Integer[][] memo;
    private Map<Character, Integer> charIndex;

    public int countVowelPermutation(int n) {
        int ans = 0;
        char[] vowels = new char[] { 'a', 'e', 'i', 'o', 'u' };
        memo = new Integer[n][5];
        charIndex = new HashMap<>();
        for (int i = 0; i < vowels.length; i++) {
            charIndex.put(vowels[i], i);
        }
        for (char vowel : vowels) {
            ans = (ans % modulo + helper(n, 0, vowel) % modulo) % modulo;
        }
        return ans % modulo;
    }

    private int helper(int n, int pos, char currChar) {
        int ans = 0, currCharIndex = charIndex.get(currChar);
        if (pos == n - 1) {
            return memo[pos][currCharIndex] = 1;
        }
        if (memo[pos][currCharIndex] != null) {
            return memo[pos][currCharIndex];
        }
        if (currChar == 'a') {
            ans = (ans % modulo + helper(n, pos + 1, 'e') % modulo) % modulo;
        } else if (currChar == 'e') {
            ans = (ans % modulo + helper(n, pos + 1, 'a') % modulo + helper(n, pos + 1, 'i') % modulo) % modulo;
        } else if (currChar == 'i') {
            ans = (ans % modulo + helper(n, pos + 1, 'a') % modulo) % modulo;
            ans = (ans % modulo + helper(n, pos + 1, 'e') % modulo) % modulo;
            ans = (ans % modulo + helper(n, pos + 1, 'o') % modulo) % modulo;
            ans = (ans % modulo + helper(n, pos + 1, 'u') % modulo) % modulo;
        } else if (currChar == 'o') {
            ans = (ans % modulo + helper(n, pos + 1, 'i') % modulo) % modulo;
            ans = (ans % modulo + helper(n, pos + 1, 'u') % modulo) % modulo;
        } else if (currChar == 'u') {
            ans = (ans % modulo + helper(n, pos + 1, 'a') % modulo) % modulo;
        }
        return memo[pos][currCharIndex] = ans;
    }
}

class Solution {
    private Integer[] memo;

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int[][] jobs = new int[startTime.length][3];
        for (int i = 0; i < startTime.length; i++) {
            jobs[i][0] = startTime[i];
            jobs[i][1] = endTime[i];
            jobs[i][2] = profit[i];
        }
        Arrays.sort(jobs, (a, b) -> a[0] - b[0]);
        memo = new Integer[jobs.length];
        return backtrack(jobs, 0);
    }

    private int backtrack(int[][] jobs, int pos) {
        if (pos == jobs.length) {
            return 0;
        }
        if (memo[pos] != null) {
            return memo[pos];
        }
        int max = 0;
        max = Math.max(backtrack(jobs, pos + 1),
                jobs[pos][2] + backtrack(jobs, binarySearch(jobs, pos + 1, jobs[pos][1])));
        ans = Math.max(ans, max);
        return memo[pos] = max;
    }

    private int binarySearch(int[][] jobs, int start, int target) {
        int left = start, right = jobs.length - 1, ans = jobs.length;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (jobs[mid][0] < target) {
                left = mid + 1;
            } else {
                ans = mid;
                right = mid - 1;
            }
        }
        return ans;
    }
}

class DetectSquares {
    Map<String, Integer> pointCount;

    public DetectSquares() {
        pointCount = new HashMap<>();
    }

    public void add(int[] point) {
        String currPoint = point[0] + "," + point[1];
        pointCount.put(currPoint, pointCount.getOrDefault(currPoint, 0) + 1);
    }

    public int count(int[] point) {
        int count = 0;
        for (Map.Entry<String, Integer> entry : pointCount.entrySet()) {
            String[] currPoint = entry.getKey().split(",");
            int x = Integer.parseInt(currPoint[0]), y = Integer.parseInt(currPoint[1]);
            if (x == point[0] || y == point[1] || Math.abs(point[0] - x) != Math.abs(point[1] - y)) {
                continue;
            }
            String targetOne = x + "," + point[1];
            String targetTwo = point[0] + "," + y;
            count += (pointCount.getOrDefault(targetOne, 0) * pointCount.getOrDefault(targetTwo, 0) * entry.getValue());
        }
        return count;
    }
}

class SparseVector {
    public List<int[]> compressed;

    SparseVector(int[] nums) {
        compressed = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            compressed.add(new int[] { i, nums[i] });
        }
    }

    // Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        int ans = 0;
        int ptrOne = 0, ptrTwo = 0;
        while (ptrOne < this.compressed.size() && ptrTwo < vec.compressed.size()) {
            if (this.compressed.get(ptrOne)[0] == vec.compressed.get(ptrTwo)[0]) {
                ans += this.compressed.get(ptrOne)[1] * vec.compressed.get(ptrTwo)[1];
                ptrOne += 1;
                ptrTwo += 1;
            } else if (this.compressed.get(ptrOne)[0] < vec.compressed.get(ptrTwo)[0]) {
                ptrOne += 1;
            } else {
                ptrTwo += 1;
            }
        }
        return ans;
    }
}