bowang0911/leetcode huggingface dataset:
Parallel Courses III

You are given an integer `n`, which indicates that there are `n` courses labeled from `1` to `n`. You are also given a 2D integer array `relations` where `relations[j] = [prevCoursej, nextCoursej]` denotes that course `prevCoursej` has to be completed **before** course `nextCoursej` (prerequisite relationship). Furthermore, you are given a **0-indexed** integer array `time` where `time[i]` denotes how many **months** it takes to complete the `(i+1)th` course.

You must find the **minimum** number of months needed to complete all the courses following these rules:

*   You may start taking a course at **any time** if the prerequisites are met.
*   **Any number of courses** can be taken at the **same time**.

Return _the **minimum** number of months needed to complete all the courses_.

**Note:** The test cases are generated such that it is possible to complete every course (i.e., the graph is a directed acyclic graph).

**Example 1:**

**Input:** n = 3, relations = \[\[1,3\],\[2,3\]\], time = \[3,2,5\]
**Output:** 8
**Explanation:** The figure above represents the given graph and the time required to complete each course. 
We start course 1 and course 2 simultaneously at month 0.
Course 1 takes 3 months and course 2 takes 2 months to complete respectively.
Thus, the earliest time we can start course 3 is at month 3, and the total time required is 3 + 5 = 8 months.

**Example 2:**

**Input:** n = 5, relations = \[\[1,5\],\[2,5\],\[3,5\],\[3,4\],\[4,5\]\], time = \[1,2,3,4,5\]
**Output:** 12
**Explanation:** The figure above represents the given graph and the time required to complete each course.
You can start courses 1, 2, and 3 at month 0.
You can complete them after 1, 2, and 3 months respectively.
Course 4 can be taken only after course 3 is completed, i.e., after 3 months. It is completed after 3 + 4 = 7 months.
Course 5 can be taken only after courses 1, 2, 3, and 4 have been completed, i.e., after max(1,2,3,7) = 7 months.
Thus, the minimum time needed to complete all the courses is 7 + 5 = 12 months.

**Constraints:**

*   `1 <= n <= 5 * 104`
*   `0 <= relations.length <= min(n * (n - 1) / 2, 5 * 104)`
*   `relations[j].length == 2`
*   `1 <= prevCoursej, nextCoursej <= n`
*   `prevCoursej != nextCoursej`
*   All the pairs `[prevCoursej, nextCoursej]` are **unique**.
*   `time.length == n`
*   `1 <= time[i] <= 104`
*   The given graph is a directed acyclic graph.
Minimum Cost to Separate Sentence Into Rows

You are given a string `sentence` containing words separated by spaces, and an integer `k`. Your task is to separate `sentence` into **rows** where the number of characters in each row is **at most** `k`. You may assume that `sentence` does not begin or end with a space, and the words in `sentence` are separated by a single space.

You can split `sentence` into rows by inserting line breaks between words in `sentence`. A word **cannot** be split between two rows. Each word must be used exactly once, and the word order cannot be rearranged. Adjacent words in a row should be separated by a single space, and rows should not begin or end with spaces.

The **cost** of a row with length `n` is `(k - n)2`, and the **total cost** is the sum of the **costs** for all rows **except** the last one.

*   For example if `sentence = "i love leetcode "` and `k = 12`:
    *   Separating `sentence` into `"i "`, `"love "`, and `"leetcode "` has a cost of `(12 - 1)2 + (12 - 4)2 = 185`.
    *   Separating `sentence` into `"i love "`, and `"leetcode "` has a cost of `(12 - 6)2 = 36`.
    *   Separating `sentence` into `"i "`, and `"love leetcode "` is not possible because the length of `"love leetcode "` is greater than `k`.

Return _the **minimum** possible total cost of separating_ `sentence` _into rows._

**Example 1:**

**Input:** sentence =  "i love leetcode ", k = 12
**Output:** 36
**Explanation:**
Separating sentence into  "i ",  "love ", and  "leetcode " has a cost of (12 - 1)2 + (12 - 4)2 = 185.
Separating sentence into  "i love ", and  "leetcode " has a cost of (12 - 6)2 = 36.
Separating sentence into  "i ",  "love leetcode " is not possible because  "love leetcode " has length 13.
36 is the minimum possible total cost so return it.

**Example 2:**

**Input:** sentence =  "apples and bananas taste great ", k = 7
**Output:** 21
**Explanation**
Separating sentence into  "apples ",  "and ",  "bananas ",  "taste ", and  "great " has a cost of (7 - 6)2 + (7 - 3)2 + (7 - 7)2 + (7 - 5)2 \= 21.
21 is the minimum possible total cost so return it.

**Example 3:**

**Input:** sentence =  "a ", k = 5
**Output:** 0
**Explanation:**
The cost of the last row is not included in the total cost, and since there is only one row, return 0.

**Constraints:**

*   `1 <= sentence.length <= 5000`
*   `1 <= k <= 5000`
*   The length of each word in `sentence` is at most `k`.
*   `sentence` consists of only lowercase English letters and spaces.
*   `sentence` does not begin or end with a space.
*   Words in `sentence` are separated by a single space.
Kth Distinct String in an Array

A **distinct string** is a string that is present only **once** in an array.

Given an array of strings `arr`, and an integer `k`, return _the_ `kth` _**distinct string** present in_ `arr`. If there are **fewer** than `k` distinct strings, return _an **empty string**_ `" "`.

Note that the strings are considered in the **order in which they appear** in the array.

**Example 1:**

**Input:** arr = \[ "d ", "b ", "c ", "b ", "c ", "a "\], k = 2
**Output:**  "a "
**Explanation:**
The only distinct strings in arr are  "d " and  "a ".
 "d " appears 1st, so it is the 1st distinct string.
 "a " appears 2nd, so it is the 2nd distinct string.
Since k == 2,  "a " is returned. 

**Example 2:**

**Input:** arr = \[ "aaa ", "aa ", "a "\], k = 1
**Output:**  "aaa "
**Explanation:**
All strings in arr are distinct, so the 1st string  "aaa " is returned.

**Example 3:**

**Input:** arr = \[ "a ", "b ", "a "\], k = 3
**Output:**  " "
**Explanation:**
The only distinct string is  "b ". Since there are fewer than 3 distinct strings, we return an empty string  " ".

**Constraints:**

*   `1 <= k <= arr.length <= 1000`
*   `1 <= arr[i].length <= 5`
*   `arr[i]` consists of lowercase English letters.
Two Best Non-Overlapping Events

You are given a **0-indexed** 2D integer array of `events` where `events[i] = [startTimei, endTimei, valuei]`. The `ith` event starts at `startTimei` and ends at `endTimei`, and if you attend this event, you will receive a value of `valuei`. You can choose **at most** **two** **non-overlapping** events to attend such that the sum of their values is **maximized**.

Return _this **maximum** sum._

Note that the start time and end time is **inclusive**: that is, you cannot attend two events where one of them starts and the other ends at the same time. More specifically, if you attend an event with end time `t`, the next event must start at or after `t + 1`.

**Example 1:**

**Input:** events = \[\[1,3,2\],\[4,5,2\],\[2,4,3\]\]
**Output:** 4
**Explanation:** Choose the green events, 0 and 1 for a sum of 2 + 2 = 4.

**Example 2:**

**Input:** events = \[\[1,3,2\],\[4,5,2\],\[1,5,5\]\]
**Output:** 5
**Explanation:** Choose event 2 for a sum of 5.

**Example 3:**

**Input:** events = \[\[1,5,3\],\[1,5,1\],\[6,6,5\]\]
**Output:** 8
**Explanation:** Choose events 0 and 2 for a sum of 3 + 5 = 8.

**Constraints:**

*   `2 <= events.length <= 105`
*   `events[i].length == 3`
*   `1 <= startTimei <= endTimei <= 109`
*   `1 <= valuei <= 106`
Plates Between Candles

There is a long table with a line of plates and candles arranged on top of it. You are given a **0-indexed** string `s` consisting of characters `'*'` and `'|'` only, where a `'*'` represents a **plate** and a `'|'` represents a **candle**.

You are also given a **0-indexed** 2D integer array `queries` where `queries[i] = [lefti, righti]` denotes the **substring** `s[lefti...righti]` (**inclusive**). For each query, you need to find the **number** of plates **between candles** that are **in the substring**. A plate is considered **between candles** if there is at least one candle to its left **and** at least one candle to its right **in the substring**.

*   For example, `s = "||**||**|* "`, and a query `[3, 8]` denotes the substring `"*||******| "`. The number of plates between candles in this substring is `2`, as each of the two plates has at least one candle **in the substring** to its left **and** right.

Return _an integer array_ `answer` _where_ `answer[i]` _is the answer to the_ `ith` _query_.

**Example 1:**

**Input:** s =  "\*\*|\*\*|\*\*\*| ", queries = \[\[2,5\],\[5,9\]\]
**Output:** \[2,3\]
**Explanation:**
- queries\[0\] has two plates between candles.
- queries\[1\] has three plates between candles.

**Example 2:**

**Input:** s =  "\*\*\*|\*\*|\*\*\*\*\*|\*\*||\*\*|\* ", queries = \[\[1,17\],\[4,5\],\[14,17\],\[5,11\],\[15,16\]\]
**Output:** \[9,0,0,0,0\]
**Explanation:**
- queries\[0\] has nine plates between candles.
- The other queries have zero plates between candles.

**Constraints:**

*   `3 <= s.length <= 105`
*   `s` consists of `'*'` and `'|'` characters.
*   `1 <= queries.length <= 105`
*   `queries[i].length == 2`
*   `0 <= lefti <= righti < s.length`
Number of Valid Move Combinations On Chessboard

There is an `8 x 8` chessboard containing `n` pieces (rooks, queens, or bishops). You are given a string array `pieces` of length `n`, where `pieces[i]` describes the type (rook, queen, or bishop) of the `ith` piece. In addition, you are given a 2D integer array `positions` also of length `n`, where `positions[i] = [ri, ci]` indicates that the `ith` piece is currently at the **1-based** coordinate `(ri, ci)` on the chessboard.

When making a **move** for a piece, you choose a **destination** square that the piece will travel toward and stop on.

*   A rook can only travel **horizontally or vertically** from `(r, c)` to the direction of `(r+1, c)`, `(r-1, c)`, `(r, c+1)`, or `(r, c-1)`.
*   A queen can only travel **horizontally, vertically, or diagonally** from `(r, c)` to the direction of `(r+1, c)`, `(r-1, c)`, `(r, c+1)`, `(r, c-1)`, `(r+1, c+1)`, `(r+1, c-1)`, `(r-1, c+1)`, `(r-1, c-1)`.
*   A bishop can only travel **diagonally** from `(r, c)` to the direction of `(r+1, c+1)`, `(r+1, c-1)`, `(r-1, c+1)`, `(r-1, c-1)`.

You must make a **move** for every piece on the board simultaneously. A **move combination** consists of all the **moves** performed on all the given pieces. Every second, each piece will instantaneously travel **one square** towards their destination if they are not already at it. All pieces start traveling at the `0th` second. A move combination is **invalid** if, at a given time, **two or more** pieces occupy the same square.

Return _the number of **valid** move combinations_​​​​​.

**Notes:**

*   **No two pieces** will start in the **same** square.
*   You may choose the square a piece is already on as its **destination**.
*   If two pieces are **directly adjacent** to each other, it is valid for them to **move past each other** and swap positions in one second.

**Example 1:**

**Input:** pieces = \[ "rook "\], positions = \[\[1,1\]\]
**Output:** 15
**Explanation:** The image above shows the possible squares the piece can move to.

**Example 2:**

**Input:** pieces = \[ "queen "\], positions = \[\[1,1\]\]
**Output:** 22
**Explanation:** The image above shows the possible squares the piece can move to.

**Example 3:**

**Input:** pieces = \[ "bishop "\], positions = \[\[4,3\]\]
**Output:** 12
**Explanation:** The image above shows the possible squares the piece can move to.

**Constraints:**

*   `n == pieces.length`
*   `n == positions.length`
*   `1 <= n <= 4`
*   `pieces` only contains the strings `"rook "`, `"queen "`, and `"bishop "`.
*   There will be at most one queen on the chessboard.
*   `1 <= xi, yi <= 8`
*   Each `positions[i]` is distinct.
Smallest Index With Equal Value

Given a **0-indexed** integer array `nums`, return _the **smallest** index_ `i` _of_ `nums` _such that_ `i mod 10 == nums[i]`_, or_ `-1` _if such index does not exist_.

`x mod y` denotes the **remainder** when `x` is divided by `y`.

**Example 1:**

**Input:** nums = \[0,1,2\]
**Output:** 0
**Explanation:** 
i=0: 0 mod 10 = 0 == nums\[0\].
i=1: 1 mod 10 = 1 == nums\[1\].
i=2: 2 mod 10 = 2 == nums\[2\].
All indices have i mod 10 == nums\[i\], so we return the smallest index 0.

**Example 2:**

**Input:** nums = \[4,3,2,1\]
**Output:** 2
**Explanation:** 
i=0: 0 mod 10 = 0 != nums\[0\].
i=1: 1 mod 10 = 1 != nums\[1\].
i=2: 2 mod 10 = 2 == nums\[2\].
i=3: 3 mod 10 = 3 != nums\[3\].
2 is the only index which has i mod 10 == nums\[i\].

**Example 3:**

**Input:** nums = \[1,2,3,4,5,6,7,8,9,0\]
**Output:** -1
**Explanation:** No index satisfies i mod 10 == nums\[i\].

**Constraints:**

*   `1 <= nums.length <= 100`
*   `0 <= nums[i] <= 9`
Find the Minimum and Maximum Number of Nodes Between Critical Points

A **critical point** in a linked list is defined as **either** a **local maxima** or a **local minima**.

A node is a **local maxima** if the current node has a value **strictly greater** than the previous node and the next node.

A node is a **local minima** if the current node has a value **strictly smaller** than the previous node and the next node.

Note that a node can only be a local maxima/minima if there exists **both** a previous node and a next node.

Given a linked list `head`, return _an array of length 2 containing_ `[minDistance, maxDistance]` _where_ `minDistance` _is the **minimum distance** between **any two distinct** critical points and_ `maxDistance` _is the **maximum distance** between **any two distinct** critical points. If there are **fewer** than two critical points, return_ `[-1, -1]`.

**Example 1:**

**Input:** head = \[3,1\]
**Output:** \[-1,-1\]
**Explanation:** There are no critical points in \[3,1\].

**Example 2:**

**Input:** head = \[5,3,1,2,5,1,2\]
**Output:** \[1,3\]
**Explanation:** There are three critical points:
- \[5,3,**1**,2,5,1,2\]: The third node is a local minima because 1 is less than 3 and 2.
- \[5,3,1,2,**5**,1,2\]: The fifth node is a local maxima because 5 is greater than 2 and 1.
- \[5,3,1,2,5,**1**,2\]: The sixth node is a local minima because 1 is less than 5 and 2.
The minimum distance is between the fifth and the sixth node. minDistance = 6 - 5 = 1.
The maximum distance is between the third and the sixth node. maxDistance = 6 - 3 = 3.

**Example 3:**

**Input:** head = \[1,3,2,2,3,2,2,2,7\]
**Output:** \[3,3\]
**Explanation:** There are two critical points:
- \[1,**3**,2,2,3,2,2,2,7\]: The second node is a local maxima because 3 is greater than 1 and 2.
- \[1,3,2,2,**3**,2,2,2,7\]: The fifth node is a local maxima because 3 is greater than 2 and 2.
Both the minimum and maximum distances are between the second and the fifth node.
Thus, minDistance and maxDistance is 5 - 2 = 3.
Note that the last node is not considered a local maxima because it does not have a next node.

**Constraints:**

*   The number of nodes in the list is in the range `[2, 105]`.
*   `1 <= Node.val <= 105`
Minimum Operations to Convert Number

You are given a **0-indexed** integer array `nums` containing **distinct** numbers, an integer `start`, and an integer `goal`. There is an integer `x` that is initially set to `start`, and you want to perform operations on `x` such that it is converted to `goal`. You can perform the following operation repeatedly on the number `x`:

If `0 <= x <= 1000`, then for any index `i` in the array (`0 <= i < nums.length`), you can set `x` to any of the following:

*   `x + nums[i]`
*   `x - nums[i]`
*   `x ^ nums[i]` (bitwise-XOR)

Note that you can use each `nums[i]` any number of times in any order. Operations that set `x` to be out of the range `0 <= x <= 1000` are valid, but no more operations can be done afterward.

Return _the **minimum** number of operations needed to convert_ `x = start` _into_ `goal`_, and_ `-1` _if it is not possible_.

**Example 1:**

**Input:** nums = \[2,4,12\], start = 2, goal = 12
**Output:** 2
**Explanation:** We can go from 2 -> 14 -> 12 with the following 2 operations.
- 2 + 12 = 14
- 14 - 2 = 12

**Example 2:**

**Input:** nums = \[3,5,7\], start = 0, goal = -4
**Output:** 2
**Explanation:** We can go from 0 -> 3 -> -4 with the following 2 operations. 
- 0 + 3 = 3
- 3 - 7 = -4
Note that the last operation sets x out of the range 0 <= x <= 1000, which is valid.

**Example 3:**

**Input:** nums = \[2,8,16\], start = 0, goal = 1
**Output:** -1
**Explanation:** There is no way to convert 0 into 1.

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `-109 <= nums[i], goal <= 109`
*   `0 <= start <= 1000`
*   `start != goal`
*   All the integers in `nums` are distinct.
Check if an Original String Exists Given Two Encoded Strings

An original string, consisting of lowercase English letters, can be encoded by the following steps:

*   Arbitrarily **split** it into a **sequence** of some number of **non-empty** substrings.
*   Arbitrarily choose some elements (possibly none) of the sequence, and **replace** each with **its length** (as a numeric string).
*   **Concatenate** the sequence as the encoded string.

For example, **one way** to encode an original string `"abcdefghijklmnop "` might be:

*   Split it as a sequence: `[ "ab ", "cdefghijklmn ", "o ", "p "]`.
*   Choose the second and third elements to be replaced by their lengths, respectively. The sequence becomes `[ "ab ", "12 ", "1 ", "p "]`.
*   Concatenate the elements of the sequence to get the encoded string: `"ab121p "`.

Given two encoded strings `s1` and `s2`, consisting of lowercase English letters and digits `1-9` (inclusive), return `true` _if there exists an original string that could be encoded as **both**_ `s1` _and_ `s2`_. Otherwise, return_ `false`.

**Note**: The test cases are generated such that the number of consecutive digits in `s1` and `s2` does not exceed `3`.

**Example 1:**

**Input:** s1 =  "internationalization ", s2 =  "i18n "
**Output:** true
**Explanation:** It is possible that  "internationalization " was the original string.
-  "internationalization " 
  -> Split:       \[ "internationalization "\]
  -> Do not replace any element
  -> Concatenate:   "internationalization ", which is s1.
-  "internationalization "
  -> Split:       \[ "i ",  "nternationalizatio ",  "n "\]
  -> Replace:     \[ "i ",  "18 ",                  "n "\]
  -> Concatenate:   "i18n ", which is s2

**Example 2:**

**Input:** s1 =  "l123e ", s2 =  "44 "
**Output:** true
**Explanation:** It is possible that  "leetcode " was the original string.
-  "leetcode " 
  -> Split:      \[ "l ",  "e ",  "et ",  "cod ",  "e "\]
  -> Replace:    \[ "l ",  "1 ",  "2 ",   "3 ",    "e "\]
  -> Concatenate:  "l123e ", which is s1.
-  "leetcode " 
  -> Split:      \[ "leet ",  "code "\]
  -> Replace:    \[ "4 ",     "4 "\]
  -> Concatenate:  "44 ", which is s2.

**Example 3:**

**Input:** s1 =  "a5b ", s2 =  "c5b "
**Output:** false
**Explanation:** It is impossible.
- The original string encoded as s1 must start with the letter 'a'.
- The original string encoded as s2 must start with the letter 'c'.

**Constraints:**

*   `1 <= s1.length, s2.length <= 40`
*   `s1` and `s2` consist of digits `1-9` (inclusive), and lowercase English letters only.
*   The number of consecutive digits in `s1` and `s2` does not exceed `3`.
Number of Spaces Cleaning Robot Cleaned

A room is represented by a **0-indexed** 2D binary matrix `room` where a `0` represents an **empty** space and a `1` represents a space with an **object**. The top left corner of the room will be empty in all test cases.

A cleaning robot starts at the top left corner of the room and is facing right. The robot will continue heading straight until it reaches the edge of the room or it hits an object, after which it will turn 90 degrees **clockwise** and repeat this process. The starting space and all spaces that the robot visits are **cleaned** by it.

Return _the number of **clean** spaces in the room if the robot runs indefinetely._

**Example 1:**  

**Input:** room = \[\[0,0,0\],\[1,1,0\],\[0,0,0\]\]
**Output:** 7
**Explanation:**
The robot cleans the spaces at (0, 0), (0, 1), and (0, 2).
The robot is at the edge of the room, so it turns 90 degrees clockwise and now faces down.
The robot cleans the spaces at (1, 2), and (2, 2).
The robot is at the edge of the room, so it turns 90 degrees clockwise and now faces left.
The robot cleans the spaces at (2, 1), and (2, 0).
The robot has cleaned all 7 empty spaces, so return 7.

**Example 2:**  

**Input:** room = \[\[0,1,0\],\[1,0,0\],\[0,0,0\]\]
**Output:** 1
**Explanation:**
The robot cleans the space at (0, 0).
The robot hits an object, so it turns 90 degrees clockwise and now faces down.
The robot hits an object, so it turns 90 degrees clockwise and now faces left.
The robot is at the edge of the room, so it turns 90 degrees clockwise and now faces up.
The robot is at the edge of the room, so it turns 90 degrees clockwise and now faces right.
The robot is back at its starting position.
The robot has cleaned 1 space, so return 1.

**Constraints:**

*   `m == room.length`
*   `n == room[r].length`
*   `1 <= m, n <= 300`
*   `room[r][c]` is either `0` or `1`.
*   `room[0][0] == 0`
Count Vowel Substrings of a String

A **substring** is a contiguous (non-empty) sequence of characters within a string.

A **vowel substring** is a substring that **only** consists of vowels (`'a'`, `'e'`, `'i'`, `'o'`, and `'u'`) and has **all five** vowels present in it.

Given a string `word`, return _the number of **vowel substrings** in_ `word`.

**Example 1:**

**Input:** word =  "aeiouu "
**Output:** 2
**Explanation:** The vowel substrings of word are as follows (underlined):
-  "**aeiou**u "
-  "**aeiouu** "

**Example 2:**

**Input:** word =  "unicornarihan "
**Output:** 0
**Explanation:** Not all 5 vowels are present, so there are no vowel substrings.

**Example 3:**

**Input:** word =  "cuaieuouac "
**Output:** 7
**Explanation:** The vowel substrings of word are as follows (underlined):
-  "c**uaieuo**uac "
-  "c**uaieuou**ac "
-  "c**uaieuoua**c "
-  "cu**aieuo**uac "
-  "cu**aieuou**ac "
-  "cu**aieuoua**c "
-  "cua**ieuoua**c "

**Constraints:**

*   `1 <= word.length <= 100`
*   `word` consists of lowercase English letters only.
Vowels of All Substrings

Given a string `word`, return _the **sum of the number of vowels** (_`'a'`, `'e'`_,_ `'i'`_,_ `'o'`_, and_ `'u'`_)_ _in every substring of_ `word`.

A **substring** is a contiguous (non-empty) sequence of characters within a string.

**Note:** Due to the large constraints, the answer may not fit in a signed 32-bit integer. Please be careful during the calculations.

**Example 1:**

**Input:** word =  "aba "
**Output:** 6
**Explanation:** 
All possible substrings are:  "a ",  "ab ",  "aba ",  "b ",  "ba ", and  "a ".
-  "b " has 0 vowels in it
-  "a ",  "ab ",  "ba ", and  "a " have 1 vowel each
-  "aba " has 2 vowels in it
Hence, the total sum of vowels = 0 + 1 + 1 + 1 + 1 + 2 = 6. 

**Example 2:**

**Input:** word =  "abc "
**Output:** 3
**Explanation:** 
All possible substrings are:  "a ",  "ab ",  "abc ",  "b ",  "bc ", and  "c ".
-  "a ",  "ab ", and  "abc " have 1 vowel each
-  "b ",  "bc ", and  "c " have 0 vowels each
Hence, the total sum of vowels = 1 + 1 + 1 + 0 + 0 + 0 = 3.

**Example 3:**

**Input:** word =  "ltcd "
**Output:** 0
**Explanation:** There are no vowels in any substring of  "ltcd ".

**Constraints:**

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