class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0, right, zeroCount = 0;
        for (right = 0; right < nums.length; right++) {
            if (nums[right] == 0)
                zeroCount += 1;
            if (zeroCount > k && nums[left++] == 0) {
                zeroCount -= 1;
            }
        }
        return right - left;
    }
}

class Solution {
    public int minAddToMakeValid(String s) {
        int leftParenCount = 0, moves = 0;
        char[] sArray = s.toCharArray();
        for (char c : sArray) {
            if (c == '(') {
                leftParenCount += 1;
            } else {
                if (leftParenCount == 0) {
                    moves += 1;
                } else {
                    leftParenCount -= 1;
                }
            }
        }
        return moves + leftParenCount;
    }
}

class Solution {
    public String customSortString(String order, String s) {
        char[] sArray = s.toCharArray();
        StringBuilder[] charCount = new StringBuilder[26];
        for (char letter : sArray) {
            if (charCount[letter - 'a'] == null) {
                charCount[letter - 'a'] = new StringBuilder();
            }
            charCount[letter - 'a'].append(letter);
        }
        char[] orderArray = order.toCharArray();
        StringBuilder ans = new StringBuilder();
        for (char letter : orderArray) {
            if (charCount[letter - 'a'] != null) {
                ans.append(charCount[letter - 'a']);
                charCount[letter - 'a'] = null;
            }
        }
        for (int i = 0; i < charCount.length; i++) {
            if (charCount[i] != null) {
                ans.append(charCount[i]);
            }
        }
        return ans.toString();
    }
}

class Solution {
    public Node insert(Node head, int insertVal) {
        Node newNode = new Node(insertVal);
        if (head == null) {
            newNode.next = newNode;
            return newNode;
        }
        if (head.next == head) {
            head.next = newNode;
            newNode.next = head;
            return head;
        }
        Node currNode = head, nextNode = head.next;
        boolean inserted = false;
        do {
            if (currNode.val <= nextNode.val) {
                if (insertVal == currNode.val || insertVal == nextNode.val
                        || (insertVal > currNode.val && insertVal < nextNode.val)) {
                    currNode.next = newNode;
                    newNode.next = nextNode;
                    inserted = true;
                    break;
                }
            } else {
                if (insertVal >= currNode.val || insertVal <= nextNode.val) {
                    currNode.next = newNode;
                    newNode.next = nextNode;
                    inserted = true;
                    break;
                }
            }
            currNode = nextNode;
            nextNode = nextNode.next;
        } while (currNode != head);
        if (inserted) {
            return head;
        }
        currNode.next = newNode;
        newNode.next = nextNode;
        return head;
    }
}

class Solution {
    public int[] exclusiveTime(int n, List<String> logs) {
        Deque<int[]> functionStack = new ArrayDeque<>();
        int start = 0, end = 0;
        functionStack.push(new int[] { -1, 0 });
        int[] ans = new int[n];
        for (String log : logs) {
            String[] info = log.split(":");
            if (info[1].equals("start")) {
                end = Integer.parseInt(info[2]);
                functionStack.peek()[1] += end - start;
                int funcId = Integer.parseInt(info[0]);
                functionStack.push(new int[] { funcId, 0 });
                start = end;
            } else {
                end = Integer.parseInt(info[2]);
                int[] topFunc = functionStack.pop();
                ans[topFunc[0]] += topFunc[1] + end - start + 1;
                start = end + 1;
            }
        }
        return ans;
    }
}

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for (int i = nums.length - 1; i >= 2; i--) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] <= nums[i]) {
                    left += 1;
                } else {
                    ans += right - left;
                    right -= 1;
                }
            }
        }
        return ans;
    }
}

class Solution {
    public String reverseWords(String s) {
        String[] words = s.split(" ");
        StringBuilder ans = new StringBuilder();
        for (String word : words) {
            StringBuilder currWord = new StringBuilder(word);
            ans.append(currWord.reverse()).append(" ");
        }
        ans.setLength(ans.length() - 1);
        return ans.toString();
    }
}

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int sum = 0;
        Map<Integer, Integer> modulo = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int currModulo = sum % k;
            if (i > 0 && currModulo == 0) {
                return true;
            }
            if (i - modulo.getOrDefault(currModulo, i) >= 2) {
                return true;
            }
            modulo.put(currModulo, modulo.getOrDefault(currModulo, i));
        }
        return false;
    }
}

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int left = 0, right, zeroCount = 0;
        for (right = 0; right < nums.length; right++) {
            if (nums[right] == 0)
                zeroCount += 1;
            if (zeroCount > 1 && nums[left++] == 0)
                zeroCount -= 1;
        }
        return right - left;
    }
}

class Solution {
    public String removeKdigits(String num, int k) {
        int[] nextSmaller = new int[num.length()];
        Arrays.fill(nextSmaller, -1);
        char[] numArray = num.toCharArray();
        Deque<Integer> monoStack = new ArrayDeque<>();
        for (int i = 0; i < numArray.length; i++) {
            while (!monoStack.isEmpty() && numArray[i] < numArray[monoStack.peek()]) {
                nextSmaller[monoStack.pop()] = i;
            }
            monoStack.push(i);
        }
        StringBuilder ans = new StringBuilder();
        int ptr = 0;
        while (ptr < nextSmaller.length) {
            if (nextSmaller[ptr] != -1 && nextSmaller[ptr] - ptr <= k) {
                k -= nextSmaller[ptr] - ptr;
                ptr = nextSmaller[ptr];
            } else {
                if (ans.length() != 0 || numArray[ptr] != '0') {
                    ans.append(numArray[ptr]);
                }
                ptr += 1;
            }
        }
        ans.setLength(Math.max(0, ans.length() - k));
        return ans.length() == 0 ? "0" : ans.toString();
    }
}