bowang0911/leetcode huggingface dataset:
Lexicographically Smallest Equivalent String

You are given two strings of the same length `s1` and `s2` and a string `baseStr`.

We say `s1[i]` and `s2[i]` are equivalent characters.

*   For example, if `s1 = "abc "` and `s2 = "cde "`, then we have `'a' == 'c'`, `'b' == 'd'`, and `'c' == 'e'`.

Equivalent characters follow the usual rules of any equivalence relation:

*   **Reflexivity:** `'a' == 'a'`.
*   **Symmetry:** `'a' == 'b'` implies `'b' == 'a'`.
*   **Transitivity:** `'a' == 'b'` and `'b' == 'c'` implies `'a' == 'c'`.

For example, given the equivalency information from `s1 = "abc "` and `s2 = "cde "`, `"acd "` and `"aab "` are equivalent strings of `baseStr = "eed "`, and `"aab "` is the lexicographically smallest equivalent string of `baseStr`.

Return _the lexicographically smallest equivalent string of_ `baseStr` _by using the equivalency information from_ `s1` _and_ `s2`.

**Example 1:**

**Input:** s1 =  "parker ", s2 =  "morris ", baseStr =  "parser "
**Output:**  "makkek "
**Explanation:** Based on the equivalency information in s1 and s2, we can group their characters as \[m,p\], \[a,o\], \[k,r,s\], \[e,i\].
The characters in each group are equivalent and sorted in lexicographical order.
So the answer is  "makkek ".

**Example 2:**

**Input:** s1 =  "hello ", s2 =  "world ", baseStr =  "hold "
**Output:**  "hdld "
**Explanation:** Based on the equivalency information in s1 and s2, we can group their characters as \[h,w\], \[d,e,o\], \[l,r\].
So only the second letter 'o' in baseStr is changed to 'd', the answer is  "hdld ".

**Example 3:**

**Input:** s1 =  "leetcode ", s2 =  "programs ", baseStr =  "sourcecode "
**Output:**  "aauaaaaada "
**Explanation:** We group the equivalent characters in s1 and s2 as \[a,o,e,r,s,c\], \[l,p\], \[g,t\] and \[d,m\], thus all letters in baseStr except 'u' and 'd' are transformed to 'a', the answer is  "aauaaaaada ".

**Constraints:**

*   `1 <= s1.length, s2.length, baseStr <= 1000`
*   `s1.length == s2.length`
*   `s1`, `s2`, and `baseStr` consist of lowercase English letters.
Longest Repeating Substring

Given a string `s`, return _the length of the longest repeating substrings_. If no repeating substring exists, return `0`.

**Example 1:**

**Input:** s =  "abcd "
**Output:** 0
**Explanation:** There is no repeating substring.

**Example 2:**

**Input:** s =  "abbaba "
**Output:** 2
**Explanation:** The longest repeating substrings are  "ab " and  "ba ", each of which occurs twice.

**Example 3:**

**Input:** s =  "aabcaabdaab "
**Output:** 3
**Explanation:** The longest repeating substring is  "aab ", which occurs `3` times.

**Constraints:**

*   `1 <= s.length <= 2000`
*   `s` consists of lowercase English letters.
Number of Valid Subarrays

Given an integer array `nums`, return _the number of non-empty **subarrays** with the leftmost element of the subarray not larger than other elements in the subarray_.

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

**Example 1:**

**Input:** nums = \[1,4,2,5,3\]
**Output:** 11
**Explanation:** There are 11 valid subarrays: \[1\],\[4\],\[2\],\[5\],\[3\],\[1,4\],\[2,5\],\[1,4,2\],\[2,5,3\],\[1,4,2,5\],\[1,4,2,5,3\].

**Example 2:**

**Input:** nums = \[3,2,1\]
**Output:** 3
**Explanation:** The 3 valid subarrays are: \[3\],\[2\],\[1\].

**Example 3:**

**Input:** nums = \[2,2,2\]
**Output:** 6
**Explanation:** There are 6 valid subarrays: \[2\],\[2\],\[2\],\[2,2\],\[2,2\],\[2,2,2\].

**Constraints:**

*   `1 <= nums.length <= 5 * 104`
*   `0 <= nums[i] <= 105`
Fixed Point

Given an array of distinct integers `arr`, where `arr` is sorted in **ascending order**, return the smallest index `i` that satisfies `arr[i] == i`. If there is no such index, return `-1`.

**Example 1:**

**Input:** arr = \[-10,-5,0,3,7\]
**Output:** 3
**Explanation:** For the given array, `arr[0] = -10, arr[1] = -5, arr[2] = 0, arr[3] = 3`, thus the output is 3.

**Example 2:**

**Input:** arr = \[0,2,5,8,17\]
**Output:** 0
**Explanation:** `arr[0] = 0`, thus the output is 0.

**Example 3:**

**Input:** arr = \[-10,-5,3,4,7,9\]
**Output:** -1
**Explanation:** There is no such `i` that `arr[i] == i`, thus the output is -1.

**Constraints:**

*   `1 <= arr.length < 104`
*   `-109 <= arr[i] <= 109`

**Follow up:** The `O(n)` solution is very straightforward. Can we do better?
Index Pairs of a String

Given a string `text` and an array of strings `words`, return _an array of all index pairs_ `[i, j]` _so that the substring_ `text[i...j]` _is in `words`_.

Return the pairs `[i, j]` in sorted order (i.e., sort them by their first coordinate, and in case of ties sort them by their second coordinate).

**Example 1:**

**Input:** text =  "thestoryofleetcodeandme ", words = \[ "story ", "fleet ", "leetcode "\]
**Output:** \[\[3,7\],\[9,13\],\[10,17\]\]

**Example 2:**

**Input:** text =  "ababa ", words = \[ "aba ", "ab "\]
**Output:** \[\[0,1\],\[0,2\],\[2,3\],\[2,4\]\]
**Explanation:** Notice that matches can overlap, see  "aba " is found in \[0,2\] and \[2,4\].

**Constraints:**

*   `1 <= text.length <= 100`
*   `1 <= words.length <= 20`
*   `1 <= words[i].length <= 50`
*   `text` and `words[i]` consist of lowercase English letters.
*   All the strings of `words` are **unique**.
Campus Bikes II

On a campus represented as a 2D grid, there are `n` workers and `m` bikes, with `n <= m`. Each worker and bike is a 2D coordinate on this grid.

We assign one unique bike to each worker so that the sum of the **Manhattan distances** between each worker and their assigned bike is minimized.

Return `the minimum possible sum of Manhattan distances between each worker and their assigned bike`.

The **Manhattan distance** between two points `p1` and `p2` is `Manhattan(p1, p2) = |p1.x - p2.x| + |p1.y - p2.y|`.

**Example 1:**

**Input:** workers = \[\[0,0\],\[2,1\]\], bikes = \[\[1,2\],\[3,3\]\]
**Output:** 6
**Explanation:** 
We assign bike 0 to worker 0, bike 1 to worker 1. The Manhattan distance of both assignments is 3, so the output is 6.

**Example 2:**

**Input:** workers = \[\[0,0\],\[1,1\],\[2,0\]\], bikes = \[\[1,0\],\[2,2\],\[2,1\]\]
**Output:** 4
**Explanation:** 
We first assign bike 0 to worker 0, then assign bike 1 to worker 1 or worker 2, bike 2 to worker 2 or worker 1. Both assignments lead to sum of the Manhattan distances as 4.

**Example 3:**

**Input:** workers = \[\[0,0\],\[1,0\],\[2,0\],\[3,0\],\[4,0\]\], bikes = \[\[0,999\],\[1,999\],\[2,999\],\[3,999\],\[4,999\]\]
**Output:** 4995

**Constraints:**

*   `n == workers.length`
*   `m == bikes.length`
*   `1 <= n <= m <= 10`
*   `workers[i].length == 2`
*   `bikes[i].length == 2`
*   `0 <= workers[i][0], workers[i][1], bikes[i][0], bikes[i][1] < 1000`
*   All the workers and the bikes locations are **unique**.
Digit Count in Range

Given a single-digit integer `d` and two integers `low` and `high`, return _the number of times that_ `d` _occurs as a digit in all integers in the inclusive range_ `[low, high]`.

**Example 1:**

**Input:** d = 1, low = 1, high = 13
**Output:** 6
**Explanation:** The digit d = 1 occurs 6 times in 1, 10, 11, 12, 13.
Note that the digit d = 1 occurs twice in the number 11.

**Example 2:**

**Input:** d = 3, low = 100, high = 250
**Output:** 35
**Explanation:** The digit d = 3 occurs 35 times in 103,113,123,130,131,...,238,239,243.

**Constraints:**

*   `0 <= d <= 9`
*   `1 <= low <= high <= 2 * 108`
Greatest Common Divisor of Strings

For two strings `s` and `t`, we say "`t` divides `s` " if and only if `s = t + ... + t` (i.e., `t` is concatenated with itself one or more times).

Given two strings `str1` and `str2`, return _the largest string_ `x` _such that_ `x` _divides both_ `str1` _and_ `str2`.

**Example 1:**

**Input:** str1 =  "ABCABC ", str2 =  "ABC "
**Output:**  "ABC "

**Example 2:**

**Input:** str1 =  "ABABAB ", str2 =  "ABAB "
**Output:**  "AB "

**Example 3:**

**Input:** str1 =  "LEET ", str2 =  "CODE "
**Output:**  " "

**Constraints:**

*   `1 <= str1.length, str2.length <= 1000`
*   `str1` and `str2` consist of English uppercase letters.
Flip Columns For Maximum Number of Equal Rows

You are given an `m x n` binary matrix `matrix`.

You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from `0` to `1` or vice versa).

Return _the maximum number of rows that have all values equal after some number of flips_.

**Example 1:**

**Input:** matrix = \[\[0,1\],\[1,1\]\]
**Output:** 1
**Explanation:** After flipping no values, 1 row has all values equal.

**Example 2:**

**Input:** matrix = \[\[0,1\],\[1,0\]\]
**Output:** 2
**Explanation:** After flipping values in the first column, both rows have equal values.

**Example 3:**

**Input:** matrix = \[\[0,0,0\],\[0,0,1\],\[1,1,0\]\]
**Output:** 2
**Explanation:** After flipping values in the first two columns, the last two rows have equal values.

**Constraints:**

*   `m == matrix.length`
*   `n == matrix[i].length`
*   `1 <= m, n <= 300`
*   `matrix[i][j]` is either `0` or `1`.
Adding Two Negabinary Numbers

Given two numbers `arr1` and `arr2` in base **\-2**, return the result of adding them together.

Each number is given in _array format_: as an array of 0s and 1s, from most significant bit to least significant bit. For example, `arr = [1,1,0,1]` represents the number `(-2)^3 + (-2)^2 + (-2)^0 = -3`. A number `arr` in _array, format_ is also guaranteed to have no leading zeros: either `arr == [0]` or `arr[0] == 1`.

Return the result of adding `arr1` and `arr2` in the same format: as an array of 0s and 1s with no leading zeros.

**Example 1:**

**Input:** arr1 = \[1,1,1,1,1\], arr2 = \[1,0,1\]
**Output:** \[1,0,0,0,0\]
**Explanation:** arr1 represents 11, arr2 represents 5, the output represents 16.

**Example 2:**

**Input:** arr1 = \[0\], arr2 = \[0\]
**Output:** \[0\]

**Example 3:**

**Input:** arr1 = \[0\], arr2 = \[1\]
**Output:** \[1\]

**Constraints:**

*   `1 <= arr1.length, arr2.length <= 1000`
*   `arr1[i]` and `arr2[i]` are `0` or `1`
*   `arr1` and `arr2` have no leading zeros
Number of Submatrices That Sum to Target

Given a `matrix` and a `target`, return the number of non-empty submatrices that sum to target.

A submatrix `x1, y1, x2, y2` is the set of all cells `matrix[x][y]` with `x1 <= x <= x2` and `y1 <= y <= y2`.

Two submatrices `(x1, y1, x2, y2)` and `(x1', y1', x2', y2')` are different if they have some coordinate that is different: for example, if `x1 != x1'`.

**Example 1:**

**Input:** matrix = \[\[0,1,0\],\[1,1,1\],\[0,1,0\]\], target = 0
**Output:** 4
**Explanation:** The four 1x1 submatrices that only contain 0.

**Example 2:**

**Input:** matrix = \[\[1,-1\],\[-1,1\]\], target = 0
**Output:** 5
**Explanation:** The two 1x2 submatrices, plus the two 2x1 submatrices, plus the 2x2 submatrix.

**Example 3:**

**Input:** matrix = \[\[904\]\], target = 0
**Output:** 0

**Constraints:**

*   `1 <= matrix.length <= 100`
*   `1 <= matrix[0].length <= 100`
*   `-1000 <= matrix[i] <= 1000`
*   `-10^8 <= target <= 10^8`
Occurrences After Bigram

Given two strings `first` and `second`, consider occurrences in some text of the form `"first second third "`, where `second` comes immediately after `first`, and `third` comes immediately after `second`.

Return _an array of all the words_ `third` _for each occurrence of_ `"first second third "`.

**Example 1:**

**Input:** text = "alice is a good girl she is a good student", first = "a", second = "good"
**Output:** \["girl","student"\]

**Example 2:**

**Input:** text = "we will we will rock you", first = "we", second = "will"
**Output:** \["we","rock"\]

**Constraints:**

*   `1 <= text.length <= 1000`
*   `text` consists of lowercase English letters and spaces.
*   All the words in `text` a separated by **a single space**.
*   `1 <= first.length, second.length <= 10`
*   `first` and `second` consist of lowercase English letters.
Letter Tile Possibilities

You have `n` `tiles`, where each tile has one letter `tiles[i]` printed on it.

Return _the number of possible non-empty sequences of letters_ you can make using the letters printed on those `tiles`.

**Example 1:**

**Input:** tiles =  "AAB "
**Output:** 8
**Explanation:** The possible sequences are  "A ",  "B ",  "AA ",  "AB ",  "BA ",  "AAB ",  "ABA ",  "BAA ".

**Example 2:**

**Input:** tiles =  "AAABBC "
**Output:** 188

**Example 3:**

**Input:** tiles =  "V "
**Output:** 1

**Constraints:**

*   `1 <= tiles.length <= 7`
*   `tiles` consists of uppercase English letters.
Insufficient Nodes in Root to Leaf Paths

Given the `root` of a binary tree and an integer `limit`, delete all **insufficient nodes** in the tree simultaneously, and return _the root of the resulting binary tree_.

A node is **insufficient** if every root to **leaf** path intersecting this node has a sum strictly less than `limit`.

A **leaf** is a node with no children.

**Example 1:**

**Input:** root = \[1,2,3,4,-99,-99,7,8,9,-99,-99,12,13,-99,14\], limit = 1
**Output:** \[1,2,3,4,null,null,7,8,9,null,14\]

**Example 2:**

**Input:** root = \[5,4,8,11,null,17,4,7,1,null,null,5,3\], limit = 22
**Output:** \[5,4,8,11,null,17,4,7,null,null,null,5\]

**Example 3:**

**Input:** root = \[1,2,-3,-5,null,4,null\], limit = -1
**Output:** \[1,null,-3,4\]

**Constraints:**

*   The number of nodes in the tree is in the range `[1, 5000]`.
*   `-105 <= Node.val <= 105`
*   `-109 <= limit <= 109`
Smallest Subsequence of Distinct Characters

Given a string `s`, return _the_ _lexicographically smallest_ _subsequence_ _of_ `s` _that contains all the distinct characters of_ `s` _exactly once_.

**Example 1:**

**Input:** s =  "bcabc "
**Output:**  "abc "

**Example 2:**

**Input:** s =  "cbacdcbc "
**Output:**  "acdb "

**Constraints:**

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

**Note:** This question is the same as 316: [https://leetcode.com/problems/remove-duplicate-letters/](https://leetcode.com/problems/remove-duplicate-letters/)
Sum of Digits in the Minimum Number

Given an integer array `nums`, return `0` _if the sum of the digits of the minimum integer in_ `nums` _is odd, or_ `1` _otherwise_.

**Example 1:**

**Input:** nums = \[34,23,1,24,75,33,54,8\]
**Output:** 0
**Explanation:** The minimal element is 1, and the sum of those digits is 1 which is odd, so the answer is 0.

**Example 2:**

**Input:** nums = \[99,77,33,66,55\]
**Output:** 1
**Explanation:** The minimal element is 33, and the sum of those digits is 3 + 3 = 6 which is even, so the answer is 1.

**Constraints:**

*   `1 <= nums.length <= 100`
*   `1 <= nums[i] <= 100`
High Five

Given a list of the scores of different students, `items`, where `items[i] = [IDi, scorei]` represents one score from a student with `IDi`, calculate each student's **top five average**.

Return _the answer as an array of pairs_ `result`_, where_ `result[j] = [IDj, topFiveAveragej]` _represents the student with_ `IDj` _and their **top five average**. Sort_ `result` _by_ `IDj` _in **increasing order**._

A student's **top five average** is calculated by taking the sum of their top five scores and dividing it by `5` using **integer division**.

**Example 1:**

**Input:** items = \[\[1,91\],\[1,92\],\[2,93\],\[2,97\],\[1,60\],\[2,77\],\[1,65\],\[1,87\],\[1,100\],\[2,100\],\[2,76\]\]
**Output:** \[\[1,87\],\[2,88\]\]
**Explanation:** 
The student with ID = 1 got scores 91, 92, 60, 65, 87, and 100. Their top five average is (100 + 92 + 91 + 87 + 65) / 5 = 87.
The student with ID = 2 got scores 93, 97, 77, 100, and 76. Their top five average is (100 + 97 + 93 + 77 + 76) / 5 = 88.6, but with integer division their average converts to 88.

**Example 2:**

**Input:** items = \[\[1,100\],\[7,100\],\[1,100\],\[7,100\],\[1,100\],\[7,100\],\[1,100\],\[7,100\],\[1,100\],\[7,100\]\]
**Output:** \[\[1,100\],\[7,100\]\]

**Constraints:**

*   `1 <= items.length <= 1000`
*   `items[i].length == 2`
*   `1 <= IDi <= 1000`
*   `0 <= scorei <= 100`
*   For each `IDi`, there will be **at least** five scores.
Brace Expansion

You are given a string `s` representing a list of words. Each letter in the word has one or more options.

*   If there is one option, the letter is represented as is.
*   If there is more than one option, then curly braces delimit the options. For example, `"{a,b,c} "` represents options `[ "a ", "b ", "c "]`.

For example, if `s = "a{b,c} "`, the first character is always `'a'`, but the second character can be `'b'` or `'c'`. The original list is `[ "ab ", "ac "]`.

Return all words that can be formed in this manner, **sorted** in lexicographical order.

**Example 1:**

**Input:** s = "{a,b}c{d,e}f"
**Output:** \["acdf","acef","bcdf","bcef"\]

**Example 2:**

**Input:** s = "abcd"
**Output:** \["abcd"\]

**Constraints:**

*   `1 <= s.length <= 50`
*   `s` consists of curly brackets `'{}'`, commas `','`, and lowercase English letters.
*   `s` is guaranteed to be a valid input.
*   There are no nested curly brackets.
*   All characters inside a pair of consecutive opening and ending curly brackets are different.
Confusing Number II

A **confusing number** is a number that when rotated `180` degrees becomes a different number with **each digit valid**.

We can rotate digits of a number by `180` degrees to form new digits.

*   When `0`, `1`, `6`, `8`, and `9` are rotated `180` degrees, they become `0`, `1`, `9`, `8`, and `6` respectively.
*   When `2`, `3`, `4`, `5`, and `7` are rotated `180` degrees, they become **invalid**.

Note that after rotating a number, we can ignore leading zeros.

*   For example, after rotating `8000`, we have `0008` which is considered as just `8`.

Given an integer `n`, return _the number of **confusing numbers** in the inclusive range_ `[1, n]`.

**Example 1:**

**Input:** n = 20
**Output:** 6
**Explanation:** The confusing numbers are \[6,9,10,16,18,19\].
6 converts to 9.
9 converts to 6.
10 converts to 01 which is just 1.
16 converts to 91.
18 converts to 81.
19 converts to 61.

**Example 2:**

**Input:** n = 100
**Output:** 19
**Explanation:** The confusing numbers are \[6,9,10,16,18,19,60,61,66,68,80,81,86,89,90,91,98,99,100\].

**Constraints:**

*   `1 <= n <= 109`
Duplicate Zeros

Given a fixed-length integer array `arr`, duplicate each occurrence of zero, shifting the remaining elements to the right.

**Note** that elements beyond the length of the original array are not written. Do the above modifications to the input array in place and do not return anything.

**Example 1:**

**Input:** arr = \[1,0,2,3,0,4,5,0\]
**Output:** \[1,0,0,2,3,0,0,4\]
**Explanation:** After calling your function, the input array is modified to: \[1,0,0,2,3,0,0,4\]

**Example 2:**

**Input:** arr = \[1,2,3\]
**Output:** \[1,2,3\]
**Explanation:** After calling your function, the input array is modified to: \[1,2,3\]

**Constraints:**

*   `1 <= arr.length <= 104`
*   `0 <= arr[i] <= 9`
Largest Values From Labels

There is a set of `n` items. You are given two integer arrays `values` and `labels` where the value and the label of the `ith` element are `values[i]` and `labels[i]` respectively. You are also given two integers `numWanted` and `useLimit`.

Choose a subset `s` of the `n` elements such that:

*   The size of the subset `s` is **less than or equal to** `numWanted`.
*   There are **at most** `useLimit` items with the same label in `s`.

The **score** of a subset is the sum of the values in the subset.

Return _the maximum **score** of a subset_ `s`.

**Example 1:**

**Input:** values = \[5,4,3,2,1\], labels = \[1,1,2,2,3\], numWanted = 3, useLimit = 1
**Output:** 9
**Explanation:** The subset chosen is the first, third, and fifth items.

**Example 2:**

**Input:** values = \[5,4,3,2,1\], labels = \[1,3,3,3,2\], numWanted = 3, useLimit = 2
**Output:** 12
**Explanation:** The subset chosen is the first, second, and third items.

**Example 3:**

**Input:** values = \[9,8,8,7,6\], labels = \[0,0,0,1,1\], numWanted = 3, useLimit = 1
**Output:** 16
**Explanation:** The subset chosen is the first and fourth items.

**Constraints:**

*   `n == values.length == labels.length`
*   `1 <= n <= 2 * 104`
*   `0 <= values[i], labels[i] <= 2 * 104`
*   `1 <= numWanted, useLimit <= n`
Shortest Path in Binary Matrix

Given an `n x n` binary matrix `grid`, return _the length of the shortest **clear path** in the matrix_. If there is no clear path, return `-1`.

A **clear path** in a binary matrix is a path from the **top-left** cell (i.e., `(0, 0)`) to the **bottom-right** cell (i.e., `(n - 1, n - 1)`) such that:

*   All the visited cells of the path are `0`.
*   All the adjacent cells of the path are **8-directionally** connected (i.e., they are different and they share an edge or a corner).

The **length of a clear path** is the number of visited cells of this path.

**Example 1:**

**Input:** grid = \[\[0,1\],\[1,0\]\]
**Output:** 2

**Example 2:**

**Input:** grid = \[\[0,0,0\],\[1,1,0\],\[1,1,0\]\]
**Output:** 4

**Example 3:**

**Input:** grid = \[\[1,0,0\],\[1,1,0\],\[1,1,0\]\]
**Output:** -1

**Constraints:**

*   `n == grid.length`
*   `n == grid[i].length`
*   `1 <= n <= 100`
*   `grid[i][j] is 0 or 1`
Shortest Common Supersequence

Given two strings `str1` and `str2`, return _the shortest string that has both_ `str1` _and_ `str2` _as **subsequences**_. If there are multiple valid strings, return **any** of them.

A string `s` is a **subsequence** of string `t` if deleting some number of characters from `t` (possibly `0`) results in the string `s`.

**Example 1:**

**Input:** str1 =  "abac ", str2 =  "cab "
**Output:**  "cabac "
**Explanation:** 
str1 =  "abac " is a subsequence of  "cabac " because we can delete the first  "c ".
str2 =  "cab " is a subsequence of  "cabac " because we can delete the last  "ac ".
The answer provided is the shortest such string that satisfies these properties.

**Example 2:**

**Input:** str1 =  "aaaaaaaa ", str2 =  "aaaaaaaa "
**Output:**  "aaaaaaaa "

**Constraints:**

*   `1 <= str1.length, str2.length <= 1000`
*   `str1` and `str2` consist of lowercase English letters.