bowang0911/leetcode huggingface dataset:
Longest Subsequence With Limited Sum

You are given an integer array `nums` of length `n`, and an integer array `queries` of length `m`.

Return _an array_ `answer` _of length_ `m` _where_ `answer[i]` _is the **maximum** size of a **subsequence** that you can take from_ `nums` _such that the **sum** of its elements is less than or equal to_ `queries[i]`.

A **subsequence** is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

**Example 1:**

**Input:** nums = \[4,5,2,1\], queries = \[3,10,21\]
**Output:** \[2,3,4\]
**Explanation:** We answer the queries as follows:
- The subsequence \[2,1\] has a sum less than or equal to 3. It can be proven that 2 is the maximum size of such a subsequence, so answer\[0\] = 2.
- The subsequence \[4,5,1\] has a sum less than or equal to 10. It can be proven that 3 is the maximum size of such a subsequence, so answer\[1\] = 3.
- The subsequence \[4,5,2,1\] has a sum less than or equal to 21. It can be proven that 4 is the maximum size of such a subsequence, so answer\[2\] = 4.

**Example 2:**

**Input:** nums = \[2,3,4,5\], queries = \[1\]
**Output:** \[0\]
**Explanation:** The empty subsequence is the only subsequence that has a sum less than or equal to 1, so answer\[0\] = 0.

**Constraints:**

*   `n == nums.length`
*   `m == queries.length`
*   `1 <= n, m <= 1000`
*   `1 <= nums[i], queries[i] <= 106`
Removing Stars From a String

You are given a string `s`, which contains stars `*`.

In one operation, you can:

*   Choose a star in `s`.
*   Remove the closest **non-star** character to its **left**, as well as remove the star itself.

Return _the string after **all** stars have been removed_.

**Note:**

*   The input will be generated such that the operation is always possible.
*   It can be shown that the resulting string will always be unique.

**Example 1:**

**Input:** s =  "leet\*\*cod\*e "
**Output:**  "lecoe "
**Explanation:** Performing the removals from left to right:
- The closest character to the 1st star is 't' in  "lee**t**\*\*cod\*e ". s becomes  "lee\*cod\*e ".
- The closest character to the 2nd star is 'e' in  "le**e**\*cod\*e ". s becomes  "lecod\*e ".
- The closest character to the 3rd star is 'd' in  "leco**d**\*e ". s becomes  "lecoe ".
There are no more stars, so we return  "lecoe ".

**Example 2:**

**Input:** s =  "erase\*\*\*\*\* "
**Output:**  " "
**Explanation:** The entire string is removed, so we return an empty string.

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists of lowercase English letters and stars `*`.
*   The operation above can be performed on `s`.
Minimum Amount of Time to Collect Garbage

You are given a **0-indexed** array of strings `garbage` where `garbage[i]` represents the assortment of garbage at the `ith` house. `garbage[i]` consists only of the characters `'M'`, `'P'` and `'G'` representing one unit of metal, paper and glass garbage respectively. Picking up **one** unit of any type of garbage takes `1` minute.

You are also given a **0-indexed** integer array `travel` where `travel[i]` is the number of minutes needed to go from house `i` to house `i + 1`.

There are three garbage trucks in the city, each responsible for picking up one type of garbage. Each garbage truck starts at house `0` and must visit each house **in order**; however, they do **not** need to visit every house.

Only **one** garbage truck may be used at any given moment. While one truck is driving or picking up garbage, the other two trucks **cannot** do anything.

Return _the **minimum** number of minutes needed to pick up all the garbage._

**Example 1:**

**Input:** garbage = \[ "G ", "P ", "GP ", "GG "\], travel = \[2,4,3\]
**Output:** 21
**Explanation:**
The paper garbage truck:
1. Travels from house 0 to house 1
2. Collects the paper garbage at house 1
3. Travels from house 1 to house 2
4. Collects the paper garbage at house 2
Altogether, it takes 8 minutes to pick up all the paper garbage.
The glass garbage truck:
1. Collects the glass garbage at house 0
2. Travels from house 0 to house 1
3. Travels from house 1 to house 2
4. Collects the glass garbage at house 2
5. Travels from house 2 to house 3
6. Collects the glass garbage at house 3
Altogether, it takes 13 minutes to pick up all the glass garbage.
Since there is no metal garbage, we do not need to consider the metal garbage truck.
Therefore, it takes a total of 8 + 13 = 21 minutes to collect all the garbage.

**Example 2:**

**Input:** garbage = \[ "MMM ", "PGM ", "GP "\], travel = \[3,10\]
**Output:** 37
**Explanation:**
The metal garbage truck takes 7 minutes to pick up all the metal garbage.
The paper garbage truck takes 15 minutes to pick up all the paper garbage.
The glass garbage truck takes 15 minutes to pick up all the glass garbage.
It takes a total of 7 + 15 + 15 = 37 minutes to collect all the garbage.

**Constraints:**

*   `2 <= garbage.length <= 105`
*   `garbage[i]` consists of only the letters `'M'`, `'P'`, and `'G'`.
*   `1 <= garbage[i].length <= 10`
*   `travel.length == garbage.length - 1`
*   `1 <= travel[i] <= 100`
Build a Matrix With Conditions

You are given a **positive** integer `k`. You are also given:

*   a 2D integer array `rowConditions` of size `n` where `rowConditions[i] = [abovei, belowi]`, and
*   a 2D integer array `colConditions` of size `m` where `colConditions[i] = [lefti, righti]`.

The two arrays contain integers from `1` to `k`.

You have to build a `k x k` matrix that contains each of the numbers from `1` to `k` **exactly once**. The remaining cells should have the value `0`.

The matrix should also satisfy the following conditions:

*   The number `abovei` should appear in a **row** that is strictly **above** the row at which the number `belowi` appears for all `i` from `0` to `n - 1`.
*   The number `lefti` should appear in a **column** that is strictly **left** of the column at which the number `righti` appears for all `i` from `0` to `m - 1`.

Return _**any** matrix that satisfies the conditions_. If no answer exists, return an empty matrix.

**Example 1:**

**Input:** k = 3, rowConditions = \[\[1,2\],\[3,2\]\], colConditions = \[\[2,1\],\[3,2\]\]
**Output:** \[\[3,0,0\],\[0,0,1\],\[0,2,0\]\]
**Explanation:** The diagram above shows a valid example of a matrix that satisfies all the conditions.
The row conditions are the following:
- Number 1 is in row 1, and number 2 is in row 2, so 1 is above 2 in the matrix.
- Number 3 is in row 0, and number 2 is in row 2, so 3 is above 2 in the matrix.
The column conditions are the following:
- Number 2 is in column 1, and number 1 is in column 2, so 2 is left of 1 in the matrix.
- Number 3 is in column 0, and number 2 is in column 1, so 3 is left of 2 in the matrix.
Note that there may be multiple correct answers.

**Example 2:**

**Input:** k = 3, rowConditions = \[\[1,2\],\[2,3\],\[3,1\],\[2,3\]\], colConditions = \[\[2,1\]\]
**Output:** \[\]
**Explanation:** From the first two conditions, 3 has to be below 1 but the third conditions needs 3 to be above 1 to be satisfied.
No matrix can satisfy all the conditions, so we return the empty matrix.

**Constraints:**

*   `2 <= k <= 400`
*   `1 <= rowConditions.length, colConditions.length <= 104`
*   `rowConditions[i].length == colConditions[i].length == 2`
*   `1 <= abovei, belowi, lefti, righti <= k`
*   `abovei != belowi`
*   `lefti != righti`
Count Strictly Increasing Subarrays

You are given an array `nums` consisting of **positive** integers.

Return _the number of **subarrays** of_ `nums` _that are in **strictly increasing** order._

A **subarray** is a **contiguous** part of an array.

**Example 1:**

**Input:** nums = \[1,3,5,4,4,6\]
**Output:** 10
**Explanation:** The strictly increasing subarrays are the following:
- Subarrays of length 1: \[1\], \[3\], \[5\], \[4\], \[4\], \[6\].
- Subarrays of length 2: \[1,3\], \[3,5\], \[4,6\].
- Subarrays of length 3: \[1,3,5\].
The total number of subarrays is 6 + 3 + 1 = 10.

**Example 2:**

**Input:** nums = \[1,2,3,4,5\]
**Output:** 15
**Explanation:** Every subarray is strictly increasing. There are 15 possible subarrays that we can take.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `1 <= nums[i] <= 106`
Find Subarrays With Equal Sum

Given a **0-indexed** integer array `nums`, determine whether there exist **two** subarrays of length `2` with **equal** sum. Note that the two subarrays must begin at **different** indices.

Return `true` _if these subarrays exist, and_ `false` _otherwise._

A **subarray** is a contiguous non-empty sequence of elements within an array.

**Example 1:**

**Input:** nums = \[4,2,4\]
**Output:** true
**Explanation:** The subarrays with elements \[4,2\] and \[2,4\] have the same sum of 6.

**Example 2:**

**Input:** nums = \[1,2,3,4,5\]
**Output:** false
**Explanation:** No two subarrays of size 2 have the same sum.

**Example 3:**

**Input:** nums = \[0,0,0\]
**Output:** true
**Explanation:** The subarrays \[nums\[0\],nums\[1\]\] and \[nums\[1\],nums\[2\]\] have the same sum of 0. 
Note that even though the subarrays have the same content, the two subarrays are considered different because they are in different positions in the original array.

**Constraints:**

*   `2 <= nums.length <= 1000`
*   `-109 <= nums[i] <= 109`
Strictly Palindromic Number

An integer `n` is **strictly palindromic** if, for **every** base `b` between `2` and `n - 2` (**inclusive**), the string representation of the integer `n` in base `b` is **palindromic**.

Given an integer `n`, return `true` _if_ `n` _is **strictly palindromic** and_ `false` _otherwise_.

A string is **palindromic** if it reads the same forward and backward.

**Example 1:**

**Input:** n = 9
**Output:** false
**Explanation:** In base 2: 9 = 1001 (base 2), which is palindromic.
In base 3: 9 = 100 (base 3), which is not palindromic.
Therefore, 9 is not strictly palindromic so we return false.
Note that in bases 4, 5, 6, and 7, n = 9 is also not palindromic.

**Example 2:**

**Input:** n = 4
**Output:** false
**Explanation:** We only consider base 2: 4 = 100 (base 2), which is not palindromic.
Therefore, we return false.

**Constraints:**

*   `4 <= n <= 105`
Maximum Rows Covered by Columns

You are given a **0-indexed** `m x n` binary matrix `matrix` and an integer `numSelect`, which denotes the number of **distinct** columns you must select from `matrix`.

Let us consider `s = {c1, c2, ...., cnumSelect}` as the set of columns selected by you. A row `row` is **covered** by `s` if:

*   For each cell `matrix[row][col]` (`0 <= col <= n - 1`) where `matrix[row][col] == 1`, `col` is present in `s` or,
*   **No cell** in `row` has a value of `1`.

You need to choose `numSelect` columns such that the number of rows that are covered is **maximized**.

Return _the **maximum** number of rows that can be **covered** by a set of_ `numSelect` _columns._

**Example 1:**

**Input:** matrix = \[\[0,0,0\],\[1,0,1\],\[0,1,1\],\[0,0,1\]\], numSelect = 2
**Output:** 3
**Explanation:** One possible way to cover 3 rows is shown in the diagram above.
We choose s = {0, 2}.
- Row 0 is covered because it has no occurrences of 1.
- Row 1 is covered because the columns with value 1, i.e. 0 and 2 are present in s.
- Row 2 is not covered because matrix\[2\]\[1\] == 1 but 1 is not present in s.
- Row 3 is covered because matrix\[2\]\[2\] == 1 and 2 is present in s.
Thus, we can cover three rows.
Note that s = {1, 2} will also cover 3 rows, but it can be shown that no more than three rows can be covered.

**Example 2:**

**Input:** matrix = \[\[1\],\[0\]\], numSelect = 1
**Output:** 2
**Explanation:** Selecting the only column will result in both rows being covered since the entire matrix is selected.
Therefore, we return 2.

**Constraints:**

*   `m == matrix.length`
*   `n == matrix[i].length`
*   `1 <= m, n <= 12`
*   `matrix[i][j]` is either `0` or `1`.
*   `1 <= numSelect <= n`
Maximum Number of Robots Within Budget

You have `n` robots. You are given two **0-indexed** integer arrays, `chargeTimes` and `runningCosts`, both of length `n`. The `ith` robot costs `chargeTimes[i]` units to charge and costs `runningCosts[i]` units to run. You are also given an integer `budget`.

The **total cost** of running `k` chosen robots is equal to `max(chargeTimes) + k * sum(runningCosts)`, where `max(chargeTimes)` is the largest charge cost among the `k` robots and `sum(runningCosts)` is the sum of running costs among the `k` robots.

Return _the **maximum** number of **consecutive** robots you can run such that the total cost **does not** exceed_ `budget`.

**Example 1:**

**Input:** chargeTimes = \[3,6,1,3,4\], runningCosts = \[2,1,3,4,5\], budget = 25
**Output:** 3
**Explanation:** 
It is possible to run all individual and consecutive pairs of robots within budget.
To obtain answer 3, consider the first 3 robots. The total cost will be max(3,6,1) + 3 \* sum(2,1,3) = 6 + 3 \* 6 = 24 which is less than 25.
It can be shown that it is not possible to run more than 3 consecutive robots within budget, so we return 3.

**Example 2:**

**Input:** chargeTimes = \[11,12,19\], runningCosts = \[10,8,7\], budget = 19
**Output:** 0
**Explanation:** No robot can be run that does not exceed the budget, so we return 0.

**Constraints:**

*   `chargeTimes.length == runningCosts.length == n`
*   `1 <= n <= 5 * 104`
*   `1 <= chargeTimes[i], runningCosts[i] <= 105`
*   `1 <= budget <= 1015`
Check Distances Between Same Letters

You are given a **0-indexed** string `s` consisting of only lowercase English letters, where each letter in `s` appears **exactly** **twice**. You are also given a **0-indexed** integer array `distance` of length `26`.

Each letter in the alphabet is numbered from `0` to `25` (i.e. `'a' -> 0`, `'b' -> 1`, `'c' -> 2`, ... , `'z' -> 25`).

In a **well-spaced** string, the number of letters between the two occurrences of the `ith` letter is `distance[i]`. If the `ith` letter does not appear in `s`, then `distance[i]` can be **ignored**.

Return `true` _if_ `s` _is a **well-spaced** string, otherwise return_ `false`.

**Example 1:**

**Input:** s =  "abaccb ", distance = \[1,3,0,5,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0\]
**Output:** true
**Explanation:**
- 'a' appears at indices 0 and 2 so it satisfies distance\[0\] = 1.
- 'b' appears at indices 1 and 5 so it satisfies distance\[1\] = 3.
- 'c' appears at indices 3 and 4 so it satisfies distance\[2\] = 0.
Note that distance\[3\] = 5, but since 'd' does not appear in s, it can be ignored.
Return true because s is a well-spaced string.

**Example 2:**

**Input:** s =  "aa ", distance = \[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0\]
**Output:** false
**Explanation:**
- 'a' appears at indices 0 and 1 so there are zero letters between them.
Because distance\[0\] = 1, s is not a well-spaced string.

**Constraints:**

*   `2 <= s.length <= 52`
*   `s` consists only of lowercase English letters.
*   Each letter appears in `s` exactly twice.
*   `distance.length == 26`
*   `0 <= distance[i] <= 50`
Number of Ways to Reach a Position After Exactly k Steps

You are given two **positive** integers `startPos` and `endPos`. Initially, you are standing at position `startPos` on an **infinite** number line. With one step, you can move either one position to the left, or one position to the right.

Given a positive integer `k`, return _the number of **different** ways to reach the position_ `endPos` _starting from_ `startPos`_, such that you perform **exactly**_ `k` _steps_. Since the answer may be very large, return it **modulo** `109 + 7`.

Two ways are considered different if the order of the steps made is not exactly the same.

**Note** that the number line includes negative integers.

**Example 1:**

**Input:** startPos = 1, endPos = 2, k = 3
**Output:** 3
**Explanation:** We can reach position 2 from 1 in exactly 3 steps in three ways:
- 1 -> 2 -> 3 -> 2.
- 1 -> 2 -> 1 -> 2.
- 1 -> 0 -> 1 -> 2.
It can be proven that no other way is possible, so we return 3.

**Example 2:**

**Input:** startPos = 2, endPos = 5, k = 10
**Output:** 0
**Explanation:** It is impossible to reach position 5 from position 2 in exactly 10 steps.

**Constraints:**

*   `1 <= startPos, endPos, k <= 1000`
Longest Nice Subarray

You are given an array `nums` consisting of **positive** integers.

We call a subarray of `nums` **nice** if the bitwise **AND** of every pair of elements that are in **different** positions in the subarray is equal to `0`.

Return _the length of the **longest** nice subarray_.

A **subarray** is a **contiguous** part of an array.

**Note** that subarrays of length `1` are always considered nice.

**Example 1:**

**Input:** nums = \[1,3,8,48,10\]
**Output:** 3
**Explanation:** The longest nice subarray is \[3,8,48\]. This subarray satisfies the conditions:
- 3 AND 8 = 0.
- 3 AND 48 = 0.
- 8 AND 48 = 0.
It can be proven that no longer nice subarray can be obtained, so we return 3.

**Example 2:**

**Input:** nums = \[3,1,5,11,13\]
**Output:** 1
**Explanation:** The length of the longest nice subarray is 1. Any subarray of length 1 can be chosen.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `1 <= nums[i] <= 109`
Meeting Rooms III

You are given an integer `n`. There are `n` rooms numbered from `0` to `n - 1`.

You are given a 2D integer array `meetings` where `meetings[i] = [starti, endi]` means that a meeting will be held during the **half-closed** time interval `[starti, endi)`. All the values of `starti` are **unique**.

Meetings are allocated to rooms in the following manner:

1.  Each meeting will take place in the unused room with the **lowest** number.
2.  If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the **same** duration as the original meeting.
3.  When a room becomes unused, meetings that have an earlier original **start** time should be given the room.

Return _the **number** of the room that held the most meetings._ If there are multiple rooms, return _the room with the **lowest** number._

A **half-closed interval** `[a, b)` is the interval between `a` and `b` **including** `a` and **not including** `b`.

**Example 1:**

**Input:** n = 2, meetings = \[\[0,10\],\[1,5\],\[2,7\],\[3,4\]\]
**Output:** 0
**Explanation:**
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period \[5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period \[10,11).
Both rooms 0 and 1 held 2 meetings, so we return 0. 

**Example 2:**

**Input:** n = 3, meetings = \[\[1,20\],\[2,10\],\[3,5\],\[4,9\],\[6,8\]\]
**Output:** 1
**Explanation:**
- At time 1, all three rooms are not being used. The first meeting starts in room 0.
- At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1.
- At time 3, only room 2 is not being used. The third meeting starts in room 2.
- At time 4, all three rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period \[5,10).
- At time 6, all three rooms are being used. The fifth meeting is delayed.
- At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period \[10,12).
Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1. 

**Constraints:**

*   `1 <= n <= 100`
*   `1 <= meetings.length <= 105`
*   `meetings[i].length == 2`
*   `0 <= starti < endi <= 5 * 105`
*   All the values of `starti` are **unique**.
Minimum Time to Kill All Monsters

You are given an integer array `power` where `power[i]` is the power of the `ith` monster.

You start with `0` mana points, and each day you increase your mana points by `gain` where `gain` initially is equal to `1`.

Each day, after gaining `gain` mana, you can defeat a monster if your mana points are greater than or equal to the power of that monster. When you defeat a monster:

*   your mana points will be reset to `0`, and
*   the value of `gain` increases by `1`.

Return _the **minimum** number of days needed to defeat all the monsters._

**Example 1:**

**Input:** power = \[3,1,4\]
**Output:** 4
**Explanation:** The optimal way to beat all the monsters is to:
- Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 2nd monster.
- Day 2: Gain 2 mana points to get a total of 2 mana points.
- Day 3: Gain 2 mana points to get a total of 4 mana points. Spend all mana points to kill the 3rd monster.
- Day 4: Gain 3 mana points to get a total of 3 mana points. Spend all mana points to kill the 1st monster.
It can be proven that 4 is the minimum number of days needed. 

**Example 2:**

**Input:** power = \[1,1,4\]
**Output:** 4
**Explanation:** The optimal way to beat all the monsters is to:
- Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 1st monster.
- Day 2: Gain 2 mana points to get a total of 2 mana points. Spend all mana points to kill the 2nd monster.
- Day 3: Gain 3 mana points to get a total of 3 mana points.
- Day 4: Gain 3 mana points to get a total of 6 mana points. Spend all mana points to kill the 3rd monster.
It can be proven that 4 is the minimum number of days needed. 

**Example 3:**

**Input:** power = \[1,2,4,9\]
**Output:** 6
**Explanation:** The optimal way to beat all the monsters is to:
- Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 1st monster.
- Day 2: Gain 2 mana points to get a total of 2 mana points. Spend all mana points to kill the 2nd monster.
- Day 3: Gain 3 mana points to get a total of 3 mana points.
- Day 4: Gain 3 mana points to get a total of 6 mana points.
- Day 5: Gain 3 mana points to get a total of 9 mana points. Spend all mana points to kill the 4th monster.
- Day 6: Gain 4 mana points to get a total of 4 mana points. Spend all mana points to kill the 3rd monster.
It can be proven that 6 is the minimum number of days needed.

**Constraints:**

*   `1 <= power.length <= 17`
*   `1 <= power[i] <= 109`
Most Frequent Even Element

Given an integer array `nums`, return _the most frequent even element_.

If there is a tie, return the **smallest** one. If there is no such element, return `-1`.

**Example 1:**

**Input:** nums = \[0,1,2,2,4,4,1\]
**Output:** 2
**Explanation:**
The even elements are 0, 2, and 4. Of these, 2 and 4 appear the most.
We return the smallest one, which is 2.

**Example 2:**

**Input:** nums = \[4,4,4,9,2,4\]
**Output:** 4
**Explanation:** 4 is the even element appears the most.

**Example 3:**

**Input:** nums = \[29,47,21,41,13,37,25,7\]
**Output:** -1
**Explanation:** There is no even element.

**Constraints:**

*   `1 <= nums.length <= 2000`
*   `0 <= nums[i] <= 105`
Optimal Partition of String

Given a string `s`, partition the string into one or more **substrings** such that the characters in each substring are **unique**. That is, no letter appears in a single substring more than **once**.

Return _the **minimum** number of substrings in such a partition._

Note that each character should belong to exactly one substring in a partition.

**Example 1:**

**Input:** s =  "abacaba "
**Output:** 4
**Explanation:**
Two possible partitions are ( "a ", "ba ", "cab ", "a ") and ( "ab ", "a ", "ca ", "ba ").
It can be shown that 4 is the minimum number of substrings needed.

**Example 2:**

**Input:** s =  "ssssss "
**Output:** 6
**Explanation:**
The only valid partition is ( "s ", "s ", "s ", "s ", "s ", "s ").

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists of only English lowercase letters.