class Solution {
    private int max;

    public int maxLength(List<String> arr) {
        int[] charOccur = new int[arr.size()];
        for (int i = 0; i < charOccur.length; i++) {
            charOccur[i] = getCharOccur(arr.get(i));
        }
        backtrack(arr, charOccur, 0, 0);
        return max;
    }

    private void backtrack(List<String> arr, int[] charOccur, int currOccur, int pos) {
        if (pos == arr.size()) {
            max = Math.max(max, getOnes(currOccur));
            return;
        }

        if (charOccur[pos] != -1 && (currOccur & charOccur[pos]) == 0) {
            backtrack(arr, charOccur, currOccur | charOccur[pos], pos + 1);
        }
        backtrack(arr, charOccur, currOccur, pos + 1);
    }

    private int getCharOccur(String s) {
        int ans = 0;
        for (char letter : s.toCharArray()) {
            int targetPos = (1 << (int) (letter - 'a'));
            if ((ans & targetPos) != 0) {
                ans = -1;
                break;
            }
            ans |= targetPos;
        }
        return ans;
    }

    private int getOnes(int num) {
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            ans += (num & 1);
            num >>= 1;
        }
        return ans;
    }
}

class Solution {
    public int[] findBall(int[][] grid) {
        int[] ans = new int[grid[0].length];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = finalPos(grid, i);
        }
        return ans;
    }

    private int finalPos(int[][] grid, int startCol) {
        int currRow = 0, currCol = startCol;
        while (currRow < grid.length && currCol < grid[0].length) {
            if (grid[currRow][currCol] == 1) {
                if (currCol == grid[0].length - 1 || grid[currRow][currCol + 1] == -1) {
                    break;
                } else {
                    currRow += 1;
                    currCol += 1;
                }
            } else {
                if (currCol == 0 || grid[currRow][currCol - 1] == 1) {
                    break;
                } else {
                    currRow += 1;
                    currCol -= 1;
                }
            }
        }
        return currRow == grid.length ? currCol : -1;
    }
}

class Solution {
    public String shiftingLetters(String s, int[] shifts) {
        long[] totalShifts = new long[shifts.length];
        long sum = 0;
        for (int i = shifts.length - 1; i >= 0; i--) {
            sum += shifts[i];
            totalShifts[i] = sum;
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            int currShift = (int) (totalShifts[i] % 26);
            int newCharAscii = s.charAt(i) + currShift;
            char newChar = newCharAscii <= 122 ? (char) newCharAscii : (char) (96 + newCharAscii % 122);
            ans.append(newChar);
        }
        return ans.toString();
    }
}

class Solution {
    private Map<Character, Integer> choices;

    public int minMutation(String start, String end, String[] bank) {
        if (start.equals(end)) {
            return 0;
        }
        choices = new HashMap<>();
        choices.put('A', 1);
        choices.put('C', 2);
        choices.put('G', 3);
        choices.put('T', 4);
        Map<Integer, String> geneHashPairs = new HashMap<>();
        for (String gene : bank) {
            geneHashPairs.putIfAbsent(getHash(gene), gene);
        }
        if (!geneHashPairs.containsKey(getHash(end))) {
            return -1;
        }
        Deque<Integer> mutations = new ArrayDeque<>();
        mutations.offer(getHash(start));
        int steps = 0;
        while (!mutations.isEmpty()) {
            for (int i = mutations.size(); i > 0; i--) {
                int currHash = mutations.poll(), offset = (int) (1e8), rollingHash = currHash;
                for (int j = 1; j < 9; j++) {
                    int currDigit = rollingHash / offset;
                    for (int k = 1; k < 5; k++) {
                        if (k == currDigit)
                            continue;
                        int newHash = currHash - (currDigit * offset) + (k * offset);
                        if (geneHashPairs.containsKey(newHash)) {
                            if (geneHashPairs.get(newHash).equals(end)) {
                                return steps + 1;
                            } else {
                                mutations.offer(newHash);
                                geneHashPairs.remove(newHash);
                            }
                        }
                    }
                    rollingHash -= (currDigit * offset);
                    offset /= 10;
                }
            }
            steps += 1;
        }
        return -1;
    }

    private int getHash(String gene) {
        int hash = 0;
        for (char letter : gene.toCharArray()) {
            hash += choices.get(letter);
            hash *= 10;
        }
        return hash;
    }
}

class Solution {
    public boolean isToeplitzMatrix(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        for (int rowStart = m - 1; rowStart >= 0; rowStart--) {
            int currRow = rowStart, currCol = 0, diagVal = matrix[currRow][currCol];
            while (currRow < m && currCol < n && matrix[currRow][currCol] == diagVal) {
                currRow += 1;
                currCol += 1;
            }
            if (currRow < m && currCol < n) {
                return false;
            }
        }

        for (int colStart = 1; colStart < n; colStart++) {
            int currRow = 0, currCol = colStart, diagVal = matrix[currRow][currCol];
            while (currRow < m && currCol < n && matrix[currRow][currCol] == diagVal) {
                currRow += 1;
                currCol += 1;
            }
            if (currRow < m && currCol < n) {
                return false;
            }
        }

        return true;
    }
}

class Solution {
    public int[] findErrorNums(int[] nums) {
        int repeat = -1;
        for (int i = 0; i < nums.length; i++) {
            int targetPos = Math.abs(nums[i]) - 1;
            if (nums[targetPos] < 0) {
                repeat = Math.abs(nums[i]);
            } else {
                nums[targetPos] *= -1;
            }
        }
        int missing = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                missing = i + 1;
            }
        }
        return new int[] { repeat, missing };
    }
}

class Solution {
    public String largestWordCount(String[] messages, String[] senders) {
        Map<String, Integer> senderWordCount = new HashMap<>();
        String maxSender = "zzzzzzzzzzz";
        int maxCount = 0;
        for (int i = 0; i < messages.length; i++) {
            senderWordCount.put(senders[i], senderWordCount.getOrDefault(senders[i], 0) + getWordCount(messages[i]));
            if (senderWordCount.get(senders[i]) > maxCount
                    || ((senderWordCount.get(senders[i]) == maxCount) && senders[i].compareTo(maxSender) > 0)) {
                maxCount = senderWordCount.get(senders[i]);
                maxSender = senders[i];
            }
        }
        return maxSender;
    }

    private int getWordCount(String message) {
        return message.split(" ").length;
    }
}

class Solution {
    public boolean checkIfPangram(String sentence) {
        int count = 0;
        for (char letter : sentence.toCharArray()) {
            count |= (1 << ((int) (letter - 'a')));
        }
        return count == ((1 << 26) - 1);
    }
}

class Solution {
    private Integer[][] memo;

    public int minDifficulty(int[] jobDifficulty, int d) {
        memo = new Integer[jobDifficulty.length][d + 1];
        int ans = backtrack(jobDifficulty, 0, d);
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

    private int backtrack(int[] diffi, int pos, int remain) {
        if (diffi.length - pos < remain) {
            return Integer.MAX_VALUE;
        }
        if (pos == diffi.length && remain == 0) {
            return 0;
        } else if (remain == 0) {
            return Integer.MAX_VALUE;
        }
        if (memo[pos][remain] != null) {
            return memo[pos][remain];
        }

        int ans = Integer.MAX_VALUE, currDifficulty = -1;
        for (int i = pos; i < diffi.length; i++) {
            currDifficulty = Math.max(currDifficulty, diffi[i]);
            int scheduleBehind = backtrack(diffi, i + 1, remain - 1);
            if (scheduleBehind != Integer.MAX_VALUE) {
                ans = Math.min(ans, currDifficulty + scheduleBehind);
            }
        }
        return memo[pos][remain] = ans;
    }
}

class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head, fast = head.next.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}