bowang0911/leetcode huggingface dataset:
Make Array Non-decreasing or Non-increasing

You are given a **0-indexed** integer array `nums`. In one operation, you can:

*   Choose an index `i` in the range `0 <= i < nums.length`
*   Set `nums[i]` to `nums[i] + 1` **or** `nums[i] - 1`

Return _the **minimum** number of operations to make_ `nums` _**non-decreasing** or **non-increasing**._

**Example 1:**

**Input:** nums = \[3,2,4,5,0\]
**Output:** 4
**Explanation:**
One possible way to turn nums into non-increasing order is to:
- Add 1 to nums\[1\] once so that it becomes 3.
- Subtract 1 from nums\[2\] once so it becomes 3.
- Subtract 1 from nums\[3\] twice so it becomes 3.
After doing the 4 operations, nums becomes \[3,3,3,3,0\] which is in non-increasing order.
Note that it is also possible to turn nums into \[4,4,4,4,0\] in 4 operations.
It can be proven that 4 is the minimum number of operations needed.

**Example 2:**

**Input:** nums = \[2,2,3,4\]
**Output:** 0
**Explanation:** nums is already in non-decreasing order, so no operations are needed and we return 0.

**Example 3:**

**Input:** nums = \[0\]
**Output:** 0
**Explanation:** nums is already in non-decreasing order, so no operations are needed and we return 0.

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `0 <= nums[i] <= 1000`

**Follow up:** Can you solve it in `O(n*log(n))` time complexity?
Largest 3-Same-Digit Number in String

You are given a string `num` representing a large integer. An integer is **good** if it meets the following conditions:

*   It is a **substring** of `num` with length `3`.
*   It consists of only one unique digit.

Return _the **maximum good** integer as a **string** or an empty string_ `" "` _if no such integer exists_.

Note:

*   A **substring** is a contiguous sequence of characters within a string.
*   There may be **leading zeroes** in `num` or a good integer.

**Example 1:**

**Input:** num =  "6**777**133339 "
**Output:**  "777 "
**Explanation:** There are two distinct good integers:  "777 " and  "333 ".
 "777 " is the largest, so we return  "777 ".

**Example 2:**

**Input:** num =  "23**000**19 "
**Output:**  "000 "
**Explanation:**  "000 " is the only good integer.

**Example 3:**

**Input:** num =  "42352338 "
**Output:**  " "
**Explanation:** No substring of length 3 consists of only one unique digit. Therefore, there are no good integers.

**Constraints:**

*   `3 <= num.length <= 1000`
*   `num` only consists of digits.
Count Nodes Equal to Average of Subtree

Given the `root` of a binary tree, return _the number of nodes where the value of the node is equal to the **average** of the values in its **subtree**_.

**Note:**

*   The **average** of `n` elements is the **sum** of the `n` elements divided by `n` and **rounded down** to the nearest integer.
*   A **subtree** of `root` is a tree consisting of `root` and all of its descendants.

**Example 1:**

**Input:** root = \[4,8,5,0,1,null,6\]
**Output:** 5
**Explanation:** 
For the node with value 4: The average of its subtree is (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4.
For the node with value 5: The average of its subtree is (5 + 6) / 2 = 11 / 2 = 5.
For the node with value 0: The average of its subtree is 0 / 1 = 0.
For the node with value 1: The average of its subtree is 1 / 1 = 1.
For the node with value 6: The average of its subtree is 6 / 1 = 6.

**Example 2:**

**Input:** root = \[1\]
**Output:** 1
**Explanation:** For the node with value 1: The average of its subtree is 1 / 1 = 1.

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 1000]`.
*   `0 <= Node.val <= 1000`
Count Number of Texts

Alice is texting Bob using her phone. The **mapping** of digits to letters is shown in the figure below.

In order to **add** a letter, Alice has to **press** the key of the corresponding digit `i` times, where `i` is the position of the letter in the key.

*   For example, to add the letter `'s'`, Alice has to press `'7'` four times. Similarly, to add the letter `'k'`, Alice has to press `'5'` twice.
*   Note that the digits `'0'` and `'1'` do not map to any letters, so Alice **does not** use them.

However, due to an error in transmission, Bob did not receive Alice's text message but received a **string of pressed keys** instead.

*   For example, when Alice sent the message `"bob "`, Bob received the string `"2266622 "`.

Given a string `pressedKeys` representing the string received by Bob, return _the **total number of possible text messages** Alice could have sent_.

Since the answer may be very large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** pressedKeys =  "22233 "
**Output:** 8
**Explanation:**
The possible text messages Alice could have sent are:
 "aaadd ",  "abdd ",  "badd ",  "cdd ",  "aaae ",  "abe ",  "bae ", and  "ce ".
Since there are 8 possible messages, we return 8.

**Example 2:**

**Input:** pressedKeys =  "222222222222222222222222222222222222 "
**Output:** 82876089
**Explanation:**
There are 2082876103 possible text messages Alice could have sent.
Since we need to return the answer modulo 109 + 7, we return 2082876103 % (109 + 7) = 82876089.

**Constraints:**

*   `1 <= pressedKeys.length <= 105`
*   `pressedKeys` only consists of digits from `'2'` - `'9'`.
Check if There Is a Valid Parentheses String Path

A parentheses string is a **non-empty** string consisting only of `'('` and `')'`. It is **valid** if **any** of the following conditions is **true**:

*   It is `()`.
*   It can be written as `AB` (`A` concatenated with `B`), where `A` and `B` are valid parentheses strings.
*   It can be written as `(A)`, where `A` is a valid parentheses string.

You are given an `m x n` matrix of parentheses `grid`. A **valid parentheses string path** in the grid is a path satisfying **all** of the following conditions:

*   The path starts from the upper left cell `(0, 0)`.
*   The path ends at the bottom-right cell `(m - 1, n - 1)`.
*   The path only ever moves **down** or **right**.
*   The resulting parentheses string formed by the path is **valid**.

Return `true` _if there exists a **valid parentheses string path** in the grid._ Otherwise, return `false`.

**Example 1:**

**Input:** grid = \[\[ "( ", "( ", "( "\],\[ ") ", "( ", ") "\],\[ "( ", "( ", ") "\],\[ "( ", "( ", ") "\]\]
**Output:** true
**Explanation:** The above diagram shows two possible paths that form valid parentheses strings.
The first path shown results in the valid parentheses string  "()(()) ".
The second path shown results in the valid parentheses string  "((())) ".
Note that there may be other valid parentheses string paths.

**Example 2:**

**Input:** grid = \[\[ ") ", ") "\],\[ "( ", "( "\]\]
**Output:** false
**Explanation:** The two possible paths form the parentheses strings  "))( " and  ")(( ". Since neither of them are valid parentheses strings, we return false.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 100`
*   `grid[i][j]` is either `'('` or `')'`.
Minimum Number of Keypresses

You have a keypad with `9` buttons, numbered from `1` to `9`, each mapped to lowercase English letters. You can choose which characters each button is matched to as long as:

*   All 26 lowercase English letters are mapped to.
*   Each character is mapped to by **exactly** `1` button.
*   Each button maps to **at most** `3` characters.

To type the first character matched to a button, you press the button once. To type the second character, you press the button twice, and so on.

Given a string `s`, return _the **minimum** number of keypresses needed to type_ `s` _using your keypad._

**Note** that the characters mapped to by each button, and the order they are mapped in cannot be changed.

**Example 1:**

**Input:** s =  "apple "
**Output:** 5
**Explanation:** One optimal way to setup your keypad is shown above.
Type 'a' by pressing button 1 once.
Type 'p' by pressing button 6 once.
Type 'p' by pressing button 6 once.
Type 'l' by pressing button 5 once.
Type 'e' by pressing button 3 once.
A total of 5 button presses are needed, so return 5.

**Example 2:**

**Input:** s =  "abcdefghijkl "
**Output:** 15
**Explanation:** One optimal way to setup your keypad is shown above.
The letters 'a' to 'i' can each be typed by pressing a button once.
Type 'j' by pressing button 1 twice.
Type 'k' by pressing button 2 twice.
Type 'l' by pressing button 3 twice.
A total of 15 button presses are needed, so return 15.

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists of lowercase English letters.
Find the K-Beauty of a Number

The **k-beauty** of an integer `num` is defined as the number of **substrings** of `num` when it is read as a string that meet the following conditions:

*   It has a length of `k`.
*   It is a divisor of `num`.

Given integers `num` and `k`, return _the k-beauty of_ `num`.

Note:

*   **Leading zeros** are allowed.
*   `0` is not a divisor of any value.

A **substring** is a contiguous sequence of characters in a string.

**Example 1:**

**Input:** num = 240, k = 2
**Output:** 2
**Explanation:** The following are the substrings of num of length k:
-  "24 " from  "**24**0 ": 24 is a divisor of 240.
-  "40 " from  "2**40** ": 40 is a divisor of 240.
Therefore, the k-beauty is 2.

**Example 2:**

**Input:** num = 430043, k = 2
**Output:** 2
**Explanation:** The following are the substrings of num of length k:
-  "43 " from  "**43**0043 ": 43 is a divisor of 430043.
-  "30 " from  "4**30**043 ": 30 is not a divisor of 430043.
-  "00 " from  "43**00**43 ": 0 is not a divisor of 430043.
-  "04 " from  "430**04**3 ": 4 is not a divisor of 430043.
-  "43 " from  "4300**43** ": 43 is a divisor of 430043.
Therefore, the k-beauty is 2.

**Constraints:**

*   `1 <= num <= 109`
*   `1 <= k <= num.length` (taking `num` as a string)
Number of Ways to Split Array

You are given a **0-indexed** integer array `nums` of length `n`.

`nums` contains a **valid split** at index `i` if the following are true:

*   The sum of the first `i + 1` elements is **greater than or equal to** the sum of the last `n - i - 1` elements.
*   There is **at least one** element to the right of `i`. That is, `0 <= i < n - 1`.

Return _the number of **valid splits** in_ `nums`.

**Example 1:**

**Input:** nums = \[10,4,-8,7\]
**Output:** 2
**Explanation:** 
There are three ways of splitting nums into two non-empty parts:
- Split nums at index 0. Then, the first part is \[10\], and its sum is 10. The second part is \[4,-8,7\], and its sum is 3. Since 10 >= 3, i = 0 is a valid split.
- Split nums at index 1. Then, the first part is \[10,4\], and its sum is 14. The second part is \[-8,7\], and its sum is -1. Since 14 >= -1, i = 1 is a valid split.
- Split nums at index 2. Then, the first part is \[10,4,-8\], and its sum is 6. The second part is \[7\], and its sum is 7. Since 6 < 7, i = 2 is not a valid split.
Thus, the number of valid splits in nums is 2.

**Example 2:**

**Input:** nums = \[2,3,1,0\]
**Output:** 2
**Explanation:** 
There are two valid splits in nums:
- Split nums at index 1. Then, the first part is \[2,3\], and its sum is 5. The second part is \[1,0\], and its sum is 1. Since 5 >= 1, i = 1 is a valid split. 
- Split nums at index 2. Then, the first part is \[2,3,1\], and its sum is 6. The second part is \[0\], and its sum is 0. Since 6 >= 0, i = 2 is a valid split.

**Constraints:**

*   `2 <= nums.length <= 105`
*   `-105 <= nums[i] <= 105`
Maximum White Tiles Covered by a Carpet

You are given a 2D integer array `tiles` where `tiles[i] = [li, ri]` represents that every tile `j` in the range `li <= j <= ri` is colored white.

You are also given an integer `carpetLen`, the length of a single carpet that can be placed **anywhere**.

Return _the **maximum** number of white tiles that can be covered by the carpet_.

**Example 1:**

**Input:** tiles = \[\[1,5\],\[10,11\],\[12,18\],\[20,25\],\[30,32\]\], carpetLen = 10
**Output:** 9
**Explanation:** Place the carpet starting on tile 10. 
It covers 9 white tiles, so we return 9.
Note that there may be other places where the carpet covers 9 white tiles.
It can be shown that the carpet cannot cover more than 9 white tiles.

**Example 2:**

**Input:** tiles = \[\[10,11\],\[1,1\]\], carpetLen = 2
**Output:** 2
**Explanation:** Place the carpet starting on tile 10. 
It covers 2 white tiles, so we return 2.

**Constraints:**

*   `1 <= tiles.length <= 5 * 104`
*   `tiles[i].length == 2`
*   `1 <= li <= ri <= 109`
*   `1 <= carpetLen <= 109`
*   The `tiles` are **non-overlapping**.
Substring With Largest Variance

The **variance** of a string is defined as the largest difference between the number of occurrences of **any** `2` characters present in the string. Note the two characters may or may not be the same.

Given a string `s` consisting of lowercase English letters only, return _the **largest variance** possible among all **substrings** of_ `s`.

A **substring** is a contiguous sequence of characters within a string.

**Example 1:**

**Input:** s =  "aababbb "
**Output:** 3
**Explanation:**
All possible variances along with their respective substrings are listed below:
- Variance 0 for substrings  "a ",  "aa ",  "ab ",  "abab ",  "aababb ",  "ba ",  "b ",  "bb ", and  "bbb ".
- Variance 1 for substrings  "aab ",  "aba ",  "abb ",  "aabab ",  "ababb ",  "aababbb ", and  "bab ".
- Variance 2 for substrings  "aaba ",  "ababbb ",  "abbb ", and  "babb ".
- Variance 3 for substring  "babbb ".
Since the largest possible variance is 3, we return it.

**Example 2:**

**Input:** s =  "abcde "
**Output:** 0
**Explanation:**
No letter occurs more than once in s, so the variance of every substring is 0.

**Constraints:**

*   `1 <= s.length <= 104`
*   `s` consists of lowercase English letters.
Find Resultant Array After Removing Anagrams

You are given a **0-indexed** string array `words`, where `words[i]` consists of lowercase English letters.

In one operation, select any index `i` such that `0 < i < words.length` and `words[i - 1]` and `words[i]` are **anagrams**, and **delete** `words[i]` from `words`. Keep performing this operation as long as you can select an index that satisfies the conditions.

Return `words` _after performing all operations_. It can be shown that selecting the indices for each operation in **any** arbitrary order will lead to the same result.

An **Anagram** is a word or phrase formed by rearranging the letters of a different word or phrase using all the original letters exactly once. For example, `"dacb "` is an anagram of `"abdc "`.

**Example 1:**

**Input:** words = \[ "abba ", "baba ", "bbaa ", "cd ", "cd "\]
**Output:** \[ "abba ", "cd "\]
**Explanation:**
One of the ways we can obtain the resultant array is by using the following operations:
- Since words\[2\] =  "bbaa " and words\[1\] =  "baba " are anagrams, we choose index 2 and delete words\[2\].
  Now words = \[ "abba ", "baba ", "cd ", "cd "\].
- Since words\[1\] =  "baba " and words\[0\] =  "abba " are anagrams, we choose index 1 and delete words\[1\].
  Now words = \[ "abba ", "cd ", "cd "\].
- Since words\[2\] =  "cd " and words\[1\] =  "cd " are anagrams, we choose index 2 and delete words\[2\].
  Now words = \[ "abba ", "cd "\].
We can no longer perform any operations, so \[ "abba ", "cd "\] is the final answer.

**Example 2:**

**Input:** words = \[ "a ", "b ", "c ", "d ", "e "\]
**Output:** \[ "a ", "b ", "c ", "d ", "e "\]
**Explanation:**
No two adjacent strings in words are anagrams of each other, so no operations are performed.

**Constraints:**

*   `1 <= words.length <= 100`
*   `1 <= words[i].length <= 10`
*   `words[i]` consists of lowercase English letters.
Maximum Consecutive Floors Without Special Floors

Alice manages a company and has rented some floors of a building as office space. Alice has decided some of these floors should be **special floors**, used for relaxation only.

You are given two integers `bottom` and `top`, which denote that Alice has rented all the floors from `bottom` to `top` (**inclusive**). You are also given the integer array `special`, where `special[i]` denotes a special floor that Alice has designated for relaxation.

Return _the **maximum** number of consecutive floors without a special floor_.

**Example 1:**

**Input:** bottom = 2, top = 9, special = \[4,6\]
**Output:** 3
**Explanation:** The following are the ranges (inclusive) of consecutive floors without a special floor:
- (2, 3) with a total amount of 2 floors.
- (5, 5) with a total amount of 1 floor.
- (7, 9) with a total amount of 3 floors.
Therefore, we return the maximum number which is 3 floors.

**Example 2:**

**Input:** bottom = 6, top = 8, special = \[7,6,8\]
**Output:** 0
**Explanation:** Every floor rented is a special floor, so we return 0.

**Constraints:**

*   `1 <= special.length <= 105`
*   `1 <= bottom <= special[i] <= top <= 109`
*   All the values of `special` are **unique**.
Largest Combination With Bitwise AND Greater Than Zero

The **bitwise AND** of an array `nums` is the bitwise AND of all integers in `nums`.

*   For example, for `nums = [1, 5, 3]`, the bitwise AND is equal to `1 & 5 & 3 = 1`.
*   Also, for `nums = [7]`, the bitwise AND is `7`.

You are given an array of positive integers `candidates`. Evaluate the **bitwise AND** of every **combination** of numbers of `candidates`. Each number in `candidates` may only be used **once** in each combination.

Return _the size of the **largest** combination of_ `candidates` _with a bitwise AND **greater** than_ `0`.

**Example 1:**

**Input:** candidates = \[16,17,71,62,12,24,14\]
**Output:** 4
**Explanation:** The combination \[16,17,62,24\] has a bitwise AND of 16 & 17 & 62 & 24 = 16 > 0.
The size of the combination is 4.
It can be shown that no combination with a size greater than 4 has a bitwise AND greater than 0.
Note that more than one combination may have the largest size.
For example, the combination \[62,12,24,14\] has a bitwise AND of 62 & 12 & 24 & 14 = 8 > 0.

**Example 2:**

**Input:** candidates = \[8,8\]
**Output:** 2
**Explanation:** The largest combination \[8,8\] has a bitwise AND of 8 & 8 = 8 > 0.
The size of the combination is 2, so we return 2.

**Constraints:**

*   `1 <= candidates.length <= 105`
*   `1 <= candidates[i] <= 107`
Count Integers in Intervals

Given an **empty** set of intervals, implement a data structure that can:

*   **Add** an interval to the set of intervals.
*   **Count** the number of integers that are present in **at least one** interval.

Implement the `CountIntervals` class:

*   `CountIntervals()` Initializes the object with an empty set of intervals.
*   `void add(int left, int right)` Adds the interval `[left, right]` to the set of intervals.
*   `int count()` Returns the number of integers that are present in **at least one** interval.

**Note** that an interval `[left, right]` denotes all the integers `x` where `left <= x <= right`.

**Example 1:**

**Input**
\[ "CountIntervals ",  "add ",  "add ",  "count ",  "add ",  "count "\]
\[\[\], \[2, 3\], \[7, 10\], \[\], \[5, 8\], \[\]\]
**Output**
\[null, null, null, 6, null, 8\]

**Explanation**
CountIntervals countIntervals = new CountIntervals(); // initialize the object with an empty set of intervals. 
countIntervals.add(2, 3);  // add \[2, 3\] to the set of intervals.
countIntervals.add(7, 10); // add \[7, 10\] to the set of intervals.
countIntervals.count();    // return 6
                           // the integers 2 and 3 are present in the interval \[2, 3\].
                           // the integers 7, 8, 9, and 10 are present in the interval \[7, 10\].
countIntervals.add(5, 8);  // add \[5, 8\] to the set of intervals.
countIntervals.count();    // return 8
                           // the integers 2 and 3 are present in the interval \[2, 3\].
                           // the integers 5 and 6 are present in the interval \[5, 8\].
                           // the integers 7 and 8 are present in the intervals \[5, 8\] and \[7, 10\].
                           // the integers 9 and 10 are present in the interval \[7, 10\].

**Constraints:**

*   `1 <= left <= right <= 109`
*   At most `105` calls **in total** will be made to `add` and `count`.
*   At least **one** call will be made to `count`.
Closest Node to Path in Tree

You are given a positive integer `n` representing the number of nodes in a tree, numbered from `0` to `n - 1` (**inclusive**). You are also given a 2D integer array `edges` of length `n - 1`, where `edges[i] = [node1i, node2i]` denotes that there is a **bidirectional** edge connecting `node1i` and `node2i` in the tree.

You are given a **0-indexed** integer array `query` of length `m` where `query[i] = [starti, endi, nodei]` means that for the `ith` query, you are tasked with finding the node on the path from `starti` to `endi` that is **closest** to `nodei`.

Return _an integer array_ `answer` _of length_ `m`_, where_ `answer[i]` _is the answer to the_ `ith` _query_.

**Example 1:**

**Input:** n = 7, edges = \[\[0,1\],\[0,2\],\[0,3\],\[1,4\],\[2,5\],\[2,6\]\], query = \[\[5,3,4\],\[5,3,6\]\]
**Output:** \[0,2\]
**Explanation:**
The path from node 5 to node 3 consists of the nodes 5, 2, 0, and 3.
The distance between node 4 and node 0 is 2.
Node 0 is the node on the path closest to node 4, so the answer to the first query is 0.
The distance between node 6 and node 2 is 1.
Node 2 is the node on the path closest to node 6, so the answer to the second query is 2.

**Example 2:**

**Input:** n = 3, edges = \[\[0,1\],\[1,2\]\], query = \[\[0,1,2\]\]
**Output:** \[1\]
**Explanation:**
The path from node 0 to node 1 consists of the nodes 0, 1.
The distance between node 2 and node 1 is 1.
Node 1 is the node on the path closest to node 2, so the answer to the first query is 1.

**Example 3:**

**Input:** n = 3, edges = \[\[0,1\],\[1,2\]\], query = \[\[0,0,0\]\]
**Output:** \[0\]
**Explanation:**
The path from node 0 to node 0 consists of the node 0.
Since 0 is the only node on the path, the answer to the first query is 0.

**Constraints:**

*   `1 <= n <= 1000`
*   `edges.length == n - 1`
*   `edges[i].length == 2`
*   `0 <= node1i, node2i <= n - 1`
*   `node1i != node2i`
*   `1 <= query.length <= 1000`
*   `query[i].length == 3`
*   `0 <= starti, endi, nodei <= n - 1`
*   The graph is a tree.
Percentage of Letter in String

Given a string `s` and a character `letter`, return _the **percentage** of characters in_ `s` _that equal_ `letter` _**rounded down** to the nearest whole percent._

**Example 1:**

**Input:** s =  "foobar ", letter =  "o "
**Output:** 33
**Explanation:**
The percentage of characters in s that equal the letter 'o' is 2 / 6 \* 100% = 33% when rounded down, so we return 33.

**Example 2:**

**Input:** s =  "jjjj ", letter =  "k "
**Output:** 0
**Explanation:**
The percentage of characters in s that equal the letter 'k' is 0%, so we return 0.

**Constraints:**

*   `1 <= s.length <= 100`
*   `s` consists of lowercase English letters.
*   `letter` is a lowercase English letter.