class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        Map<Integer, List<List<Integer>>> neighborMap = new HashMap<>();
        for (int[] time : times) {
            neighborMap.putIfAbsent(time[0], new ArrayList<>());
            neighborMap.get(time[0]).add(new ArrayList<>(Arrays.asList(time[1], time[2])));
        }
        PriorityQueue<Pair<Integer, Integer>> q = new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
        q.offer(new Pair<>(k, 0));
        Set<Integer> visited = new HashSet<>();
        int ans = -1;
        while (!q.isEmpty()) {
            Pair<Integer, Integer> currPair = q.poll();
            if (visited.contains(currPair.getKey())) {
                continue;
            }
            visited.add(currPair.getKey());
            ans = Math.max(ans, currPair.getValue());
            if (visited.size() == n) {
                return ans;
            }
            if (neighborMap.containsKey(currPair.getKey())) {
                for (List<Integer> neighbor : neighborMap.get(currPair.getKey())) {
                    q.offer(new Pair<>(neighbor.get(0), neighbor.get(1) + currPair.getValue()));
                }
            }
        }
        return -1;
    }
}

class SmallestInfiniteSet {
    int count;
    TreeSet<Integer> set;

    public SmallestInfiniteSet() {
        count = 1;
        set = new TreeSet<>();
    }

    // O(1)时间复杂度
    public int popSmallest() {
        if (set.isEmpty()) {
            return count++;
        } else {
            return set.pollFirst();
        }
    }

    // O(logn)
    public void addBack(int num) {
        if (num < count && set.add(num)) {
            return;
        }
    }
}

class Solution {
    public int minSetSize(int[] arr) {
        Map<Integer, Integer> numCount = new HashMap<>();
        int maxCount = 0;
        for (int num : arr) {
            numCount.put(num, numCount.getOrDefault(num, 0) + 1);
            maxCount = Math.max(maxCount, numCount.get(num));
        }
        List<List<Integer>> bucket = new ArrayList<>();
        for (int i = 0; i <= maxCount; i++) {
            bucket.add(new ArrayList<>());
        }
        for (Map.Entry<Integer, Integer> entry : numCount.entrySet()) {
            int num = entry.getKey();
            int count = entry.getValue();
            bucket.get(count).add(num);
        }
        int remain = arr.length;
        int removedCount = 0;
        for (int i = bucket.size() - 1; i >= 0; i--) {
            for (int num : bucket.get(i)) {
                if (remain > arr.length / 2) {
                    removedCount += 1;
                    remain -= i;
                } else {
                    break;
                }
            }
            if (remain <= arr.length / 2) {
                break;
            }
        }
        return removedCount;
    }
}

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] memo = new int[text1.length() + 1][text2.length() + 1];
        for (int i = 0; i < text1.length(); i++) {
            for (int j = 0; j < text2.length(); j++) {
                memo[i][j] = -1;
            }
        }
        return helper(text1, text2, 0, 0, memo);
    }

    private int helper(String text1, String text2, int pos1, int pos2, int[][] memo) {
        if (memo[pos1][pos2] != -1) {
            return memo[pos1][pos2];
        }
        int option1 = helper(text1, text2, pos1 + 1, pos2, memo);
        int option2 = 0;
        int firstOccurence = text2.indexOf(text1.charAt(pos1), pos2);
        if (firstOccurence != -1) {
            option2 = helper(text1, text2, pos1 + 1, firstOccurence + 1, memo) + 1;
        }
        memo[pos1][pos2] = Math.max(option1, option2);
        return memo[pos1][pos2];
    }
}

class Solution {
    private static class Pair {
        ListNode node;
        int idx;

        Pair(ListNode _node, int _idx) {
            node = _node;
            idx = _idx;
        }
    }

    public int[] nextLargerNodes(ListNode head) {
        Stack<Pair> stack = new Stack<>();
        ListNode ptr = head;

        // Get the list size
        int listSize = 0;
        while (ptr != null) {
            listSize += 1;
            ptr = ptr.next;
        }

        int[] ans = new int[listSize];
        int idx = 0;
        ptr = head;
        while (ptr != null) {
            while (!stack.isEmpty() && ptr.val > stack.peek().node.val) {
                ans[stack.pop().idx] = ptr.val;
            }
            stack.push(new Pair(ptr, idx));
            idx += 1;
            ptr = ptr.next;
        }
        return ans;
    }
}

class Solution {
    static private class Info {
        int xDepth;
        int yDepth;
        TreeNode xParent;
        TreeNode yParent;
    }

    public boolean isCousins(TreeNode root, int x, int y) {
        Info info = new Info();
        dfs(root, null, x, y, 0, info);
        if (info.xDepth == info.yDepth && info.xParent != info.yParent) {
            return true;
        }
        return false;
    }

    private void dfs(TreeNode node, TreeNode parent, int x, int y, int depth, Info info) {
        if (node == null) {
            return;
        }
        if (node.val == x) {
            info.xDepth = depth;
            info.xParent = parent;
        } else if (node.val == y) {
            info.yDepth = depth;
            info.yParent = parent;
        }
        dfs(node.left, node, x, y, depth + 1, info);
        dfs(node.right, node, x, y, depth + 1, info);
    }
}

class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        Map<TreeNode, TreeNode> parentMap = new HashMap<>();
        dfs(root, null, parentMap);
        List<Integer> ans = new ArrayList<>();
        bfs(target, k, parentMap, ans);
        return ans;
    }

    private void dfs(TreeNode node, TreeNode parent, Map<TreeNode, TreeNode> parentMap) {
        parentMap.put(node, parent);
        if (node.left != null) {
            dfs(node.left, node, parentMap);
        }
        if (node.right != null) {
            dfs(node.right, node, parentMap);
        }
    }

    private void bfs(TreeNode target, int k, Map<TreeNode, TreeNode> parentMap, List<Integer> ans) {
        if (k == 0) {
            ans.add(target.val);
            return;
        }
        int currDistance = 0;
        Queue<TreeNode> q = new LinkedList<>();
        Set<TreeNode> visited = new HashSet<>();
        q.add(target);
        visited.add(target);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode currNode = q.poll();
                if (currNode.left != null && visited.add(currNode.left)) {
                    q.offer(currNode.left);
                }
                if (currNode.right != null && visited.add(currNode.right)) {
                    q.offer(currNode.right);
                }
                if (parentMap.get(currNode) != null && visited.add(parentMap.get(currNode))) {
                    q.offer(parentMap.get(currNode));
                }
            }
            currDistance += 1;
            if (currDistance == k) {
                break;
            }
        }
        if (currDistance == k) {
            while (!q.isEmpty()) {
                ans.add(q.poll().val);
            }
        }
    }
}

class Solution {
    public int uniqueMorseRepresentations(String[] words) {
        String[] morseCode = new String[] { ".-", "-...", "-.-.", "-..", ".", "..-.", "--.", "....", "..", ".---",
                "-.-", ".-..", "--", "-.", "---", ".--.", "--.-", ".-.", "...", "-", "..-", "...-", ".--", "-..-",
                "-.--", "--.." };
        Set<String> transformationSet = new HashSet<>();
        for (String word : words) {
            StringBuilder currTransformation = new StringBuilder();
            for (char c : word.toCharArray()) {
                currTransformation.append(morseCode[c - 'a']);
            }
            transformationSet.add(currTransformation.toString());
        }
        return transformationSet.size();
    }
}

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] lastIdx = new int[26];
        for (int i = 0; i < s.length(); i++) {
            lastIdx[s.charAt(i) - 'a'] = i;
        }
        int pos = 0;
        List<Integer> ans = new ArrayList<>();
        while (pos < s.length()) {
            int leftBound = pos;
            int rightBound = pos;
            while (pos <= rightBound) {
                rightBound = Math.max(lastIdx[s.charAt(pos) - 'a'], rightBound);
                pos += 1;
            }
            ans.add(rightBound - leftBound + 1);
        }
        return ans;
    }
}

class Solution {
    public int countSubstrings(String s) {
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            ans += palindromeCountAroundCenter(s, i, i);
            ans += palindromeCountAroundCenter(s, i, i + 1);
        }
        return ans;
    }

    private int palindromeCountAroundCenter(String s, int left, int right) {
        int ans = 0;
        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) != s.charAt(right)) {
                break;
            }
            left -= 1;
            right += 1;
            ans += 1;
        }
        return ans;
    }
}