bowang0911/leetcode huggingface dataset:
Concatenation of Array

Given an integer array `nums` of length `n`, you want to create an array `ans` of length `2n` where `ans[i] == nums[i]` and `ans[i + n] == nums[i]` for `0 <= i < n` (**0-indexed**).

Specifically, `ans` is the **concatenation** of two `nums` arrays.

Return _the array_ `ans`.

**Example 1:**

**Input:** nums = \[1,2,1\]
**Output:** \[1,2,1,1,2,1\]
**Explanation:** The array ans is formed as follows:
- ans = \[nums\[0\],nums\[1\],nums\[2\],nums\[0\],nums\[1\],nums\[2\]\]
- ans = \[1,2,1,1,2,1\]

**Example 2:**

**Input:** nums = \[1,3,2,1\]
**Output:** \[1,3,2,1,1,3,2,1\]
**Explanation:** The array ans is formed as follows:
- ans = \[nums\[0\],nums\[1\],nums\[2\],nums\[3\],nums\[0\],nums\[1\],nums\[2\],nums\[3\]\]
- ans = \[1,3,2,1,1,3,2,1\]

**Constraints:**

*   `n == nums.length`
*   `1 <= n <= 1000`
*   `1 <= nums[i] <= 1000`
Unique Length-3 Palindromic Subsequences

Given a string `s`, return _the number of **unique palindromes of length three** that are a **subsequence** of_ `s`.

Note that even if there are multiple ways to obtain the same subsequence, it is still only counted **once**.

A **palindrome** is a string that reads the same forwards and backwards.

A **subsequence** of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

*   For example, `"ace "` is a subsequence of `"abcde "`.

**Example 1:**

**Input:** s =  "aabca "
**Output:** 3
**Explanation:** The 3 palindromic subsequences of length 3 are:
-  "aba " (subsequence of  "aabca ")
-  "aaa " (subsequence of  "aabca ")
-  "aca " (subsequence of  "aabca ")

**Example 2:**

**Input:** s =  "adc "
**Output:** 0
**Explanation:** There are no palindromic subsequences of length 3 in  "adc ".

**Example 3:**

**Input:** s =  "bbcbaba "
**Output:** 4
**Explanation:** The 4 palindromic subsequences of length 3 are:
-  "bbb " (subsequence of  "bbcbaba ")
-  "bcb " (subsequence of  "bbcbaba ")
-  "bab " (subsequence of  "bbcbaba ")
-  "aba " (subsequence of  "bbcbaba ")

**Constraints:**

*   `3 <= s.length <= 105`
*   `s` consists of only lowercase English letters.
Painting a Grid With Three Different Colors

You are given two integers `m` and `n`. Consider an `m x n` grid where each cell is initially white. You can paint each cell **red**, **green**, or **blue**. All cells **must** be painted.

Return _the number of ways to color the grid with **no two adjacent cells having the same color**_. Since the answer can be very large, return it **modulo** `109 + 7`.

**Example 1:**

**Input:** m = 1, n = 1
**Output:** 3
**Explanation:** The three possible colorings are shown in the image above.

**Example 2:**

**Input:** m = 1, n = 2
**Output:** 6
**Explanation:** The six possible colorings are shown in the image above.

**Example 3:**

**Input:** m = 5, n = 5
**Output:** 580986

**Constraints:**

*   `1 <= m <= 5`
*   `1 <= n <= 1000`
Merge BSTs to Create Single BST

You are given `n` **BST (binary search tree) root nodes** for `n` separate BSTs stored in an array `trees` (**0-indexed**). Each BST in `trees` has **at most 3 nodes**, and no two roots have the same value. In one operation, you can:

*   Select two **distinct** indices `i` and `j` such that the value stored at one of the **leaves** of `trees[i]` is equal to the **root value** of `trees[j]`.
*   Replace the leaf node in `trees[i]` with `trees[j]`.
*   Remove `trees[j]` from `trees`.

Return _the **root** of the resulting BST if it is possible to form a valid BST after performing_ `n - 1` _operations, or_ `null` _if it is impossible to create a valid BST_.

A BST (binary search tree) is a binary tree where each node satisfies the following property:

*   Every node in the node's left subtree has a value **strictly less** than the node's value.
*   Every node in the node's right subtree has a value **strictly greater** than the node's value.

A leaf is a node that has no children.

**Example 1:**

**Input:** trees = \[\[2,1\],\[3,2,5\],\[5,4\]\]
**Output:** \[3,2,5,1,null,4\]
**Explanation:**
In the first operation, pick i=1 and j=0, and merge trees\[0\] into trees\[1\].
Delete trees\[0\], so trees = \[\[3,2,5,1\],\[5,4\]\].
 
In the second operation, pick i=0 and j=1, and merge trees\[1\] into trees\[0\].
Delete trees\[1\], so trees = \[\[3,2,5,1,null,4\]\].
 
The resulting tree, shown above, is a valid BST, so return its root.

**Example 2:**

**Input:** trees = \[\[5,3,8\],\[3,2,6\]\]
**Output:** \[\]
**Explanation:**
Pick i=0 and j=1 and merge trees\[1\] into trees\[0\].
Delete trees\[1\], so trees = \[\[5,3,8,2,6\]\].
 
The resulting tree is shown above. This is the only valid operation that can be performed, but the resulting tree is not a valid BST, so return null.

**Example 3:**

**Input:** trees = \[\[5,4\],\[3\]\]
**Output:** \[\]
**Explanation:** It is impossible to perform any operations.

**Constraints:**

*   `n == trees.length`
*   `1 <= n <= 5 * 104`
*   The number of nodes in each tree is in the range `[1, 3]`.
*   Each node in the input may have children but no grandchildren.
*   No two roots of `trees` have the same value.
*   All the trees in the input are **valid BSTs**.
*   `1 <= TreeNode.val <= 5 * 104`.
Check if String Is Decomposable Into Value-Equal Substrings

A **value-equal** string is a string where **all** characters are the same.

*   For example, `"1111 "` and `"33 "` are value-equal strings.
*   In contrast, `"123 "` is not a value-equal string.

Given a digit string `s`, decompose the string into some number of **consecutive value-equal** substrings where **exactly one** substring has a **length of** `2` and the remaining substrings have a **length of** `3`.

Return `true` _if you can decompose_ `s` _according to the above rules. Otherwise, return_ `false`.

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

**Example 1:**

**Input:** s =  "000111000 "
**Output:** false
**Explanation:** s cannot be decomposed according to the rules because \[ "000 ",  "111 ",  "000 "\] does not have a substring of length 2.

**Example 2:**

**Input:** s =  "00011111222 "
**Output:** true
**Explanation:** s can be decomposed into \[ "000 ",  "111 ",  "11 ",  "222 "\].

**Example 3:**

**Input:** s =  "011100022233 "
**Output:** false
**Explanation:** s cannot be decomposed according to the rules because of the first '0'.

**Constraints:**

*   `1 <= s.length <= 1000`
*   `s` consists of only digits `'0'` through `'9'`.
Maximum Number of Words You Can Type

There is a malfunctioning keyboard where some letter keys do not work. All other keys on the keyboard work properly.

Given a string `text` of words separated by a single space (no leading or trailing spaces) and a string `brokenLetters` of all **distinct** letter keys that are broken, return _the **number of words** in_ `text` _you can fully type using this keyboard_.

**Example 1:**

**Input:** text =  "hello world ", brokenLetters =  "ad "
**Output:** 1
**Explanation:** We cannot type  "world " because the 'd' key is broken.

**Example 2:**

**Input:** text =  "leet code ", brokenLetters =  "lt "
**Output:** 1
**Explanation:** We cannot type  "leet " because the 'l' and 't' keys are broken.

**Example 3:**

**Input:** text =  "leet code ", brokenLetters =  "e "
**Output:** 0
**Explanation:** We cannot type either word because the 'e' key is broken.

**Constraints:**

*   `1 <= text.length <= 104`
*   `0 <= brokenLetters.length <= 26`
*   `text` consists of words separated by a single space without any leading or trailing spaces.
*   Each word only consists of lowercase English letters.
*   `brokenLetters` consists of **distinct** lowercase English letters.
Add Minimum Number of Rungs

You are given a **strictly increasing** integer array `rungs` that represents the **height** of rungs on a ladder. You are currently on the **floor** at height `0`, and you want to reach the last rung.

You are also given an integer `dist`. You can only climb to the next highest rung if the distance between where you are currently at (the floor or on a rung) and the next rung is **at most** `dist`. You are able to insert rungs at any positive **integer** height if a rung is not already there.

Return _the **minimum** number of rungs that must be added to the ladder in order for you to climb to the last rung._

**Example 1:**

**Input:** rungs = \[1,3,5,10\], dist = 2
**Output:** 2
**Explanation:**
You currently cannot reach the last rung.
Add rungs at heights 7 and 8 to climb this ladder. 
The ladder will now have rungs at \[1,3,5,7,8,10\].

**Example 2:**

**Input:** rungs = \[3,6,8,10\], dist = 3
**Output:** 0
**Explanation:**
This ladder can be climbed without adding additional rungs.

**Example 3:**

**Input:** rungs = \[3,4,6,7\], dist = 2
**Output:** 1
**Explanation:**
You currently cannot reach the first rung from the ground.
Add a rung at height 1 to climb this ladder.
The ladder will now have rungs at \[1,3,4,6,7\].

**Constraints:**

*   `1 <= rungs.length <= 105`
*   `1 <= rungs[i] <= 109`
*   `1 <= dist <= 109`
*   `rungs` is **strictly increasing**.
Maximum Number of Points with Cost

You are given an `m x n` integer matrix `points` (**0-indexed**). Starting with `0` points, you want to **maximize** the number of points you can get from the matrix.

To gain points, you must pick one cell in **each row**. Picking the cell at coordinates `(r, c)` will **add** `points[r][c]` to your score.

However, you will lose points if you pick a cell too far from the cell that you picked in the previous row. For every two adjacent rows `r` and `r + 1` (where `0 <= r < m - 1`), picking cells at coordinates `(r, c1)` and `(r + 1, c2)` will **subtract** `abs(c1 - c2)` from your score.

Return _the **maximum** number of points you can achieve_.

`abs(x)` is defined as:

*   `x` for `x >= 0`.
*   `-x` for `x < 0`.

**Example 1:**

**Input:** points = \[\[1,2,3\],\[1,5,1\],\[3,1,1\]\]
**Output:** 9
**Explanation:**
The blue cells denote the optimal cells to pick, which have coordinates (0, 2), (1, 1), and (2, 0).
You add 3 + 5 + 3 = 11 to your score.
However, you must subtract abs(2 - 1) + abs(1 - 0) = 2 from your score.
Your final score is 11 - 2 = 9.

**Example 2:**

**Input:** points = \[\[1,5\],\[2,3\],\[4,2\]\]
**Output:** 11
**Explanation:**
The blue cells denote the optimal cells to pick, which have coordinates (0, 1), (1, 1), and (2, 0).
You add 5 + 3 + 4 = 12 to your score.
However, you must subtract abs(1 - 1) + abs(1 - 0) = 1 from your score.
Your final score is 12 - 1 = 11.

**Constraints:**

*   `m == points.length`
*   `n == points[r].length`
*   `1 <= m, n <= 105`
*   `1 <= m * n <= 105`
*   `0 <= points[r][c] <= 105`
Maximum Genetic Difference Query

There is a rooted tree consisting of `n` nodes numbered `0` to `n - 1`. Each node's number denotes its **unique genetic value** (i.e. the genetic value of node `x` is `x`). The **genetic difference** between two genetic values is defined as the **bitwise-****XOR** of their values. You are given the integer array `parents`, where `parents[i]` is the parent for node `i`. If node `x` is the **root** of the tree, then `parents[x] == -1`.

You are also given the array `queries` where `queries[i] = [nodei, vali]`. For each query `i`, find the **maximum genetic difference** between `vali` and `pi`, where `pi` is the genetic value of any node that is on the path between `nodei` and the root (including `nodei` and the root). More formally, you want to maximize `vali XOR pi`.

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

**Example 1:**

**Input:** parents = \[-1,0,1,1\], queries = \[\[0,2\],\[3,2\],\[2,5\]\]
**Output:** \[2,3,7\]
**Explanation:** The queries are processed as follows:
- \[0,2\]: The node with the maximum genetic difference is 0, with a difference of 2 XOR 0 = 2.
- \[3,2\]: The node with the maximum genetic difference is 1, with a difference of 2 XOR 1 = 3.
- \[2,5\]: The node with the maximum genetic difference is 2, with a difference of 5 XOR 2 = 7.

**Example 2:**

**Input:** parents = \[3,7,-1,2,0,7,0,2\], queries = \[\[4,6\],\[1,15\],\[0,5\]\]
**Output:** \[6,14,7\]
**Explanation:** The queries are processed as follows:
- \[4,6\]: The node with the maximum genetic difference is 0, with a difference of 6 XOR 0 = 6.
- \[1,15\]: The node with the maximum genetic difference is 1, with a difference of 15 XOR 1 = 14.
- \[0,5\]: The node with the maximum genetic difference is 2, with a difference of 5 XOR 2 = 7.

**Constraints:**

*   `2 <= parents.length <= 105`
*   `0 <= parents[i] <= parents.length - 1` for every node `i` that is **not** the root.
*   `parents[root] == -1`
*   `1 <= queries.length <= 3 * 104`
*   `0 <= nodei <= parents.length - 1`
*   `0 <= vali <= 2 * 105`
Check if All Characters Have Equal Number of Occurrences

Given a string `s`, return `true` _if_ `s` _is a **good** string, or_ `false` _otherwise_.

A string `s` is **good** if **all** the characters that appear in `s` have the **same** number of occurrences (i.e., the same frequency).

**Example 1:**

**Input:** s =  "abacbc "
**Output:** true
**Explanation:** The characters that appear in s are 'a', 'b', and 'c'. All characters occur 2 times in s.

**Example 2:**

**Input:** s =  "aaabb "
**Output:** false
**Explanation:** The characters that appear in s are 'a' and 'b'.
'a' occurs 3 times while 'b' occurs 2 times, which is not the same number of times.

**Constraints:**

*   `1 <= s.length <= 1000`
*   `s` consists of lowercase English letters.
The Number of the Smallest Unoccupied Chair

There is a party where `n` friends numbered from `0` to `n - 1` are attending. There is an **infinite** number of chairs in this party that are numbered from `0` to `infinity`. When a friend arrives at the party, they sit on the unoccupied chair with the **smallest number**.

*   For example, if chairs `0`, `1`, and `5` are occupied when a friend comes, they will sit on chair number `2`.

When a friend leaves the party, their chair becomes unoccupied at the moment they leave. If another friend arrives at that same moment, they can sit in that chair.

You are given a **0-indexed** 2D integer array `times` where `times[i] = [arrivali, leavingi]`, indicating the arrival and leaving times of the `ith` friend respectively, and an integer `targetFriend`. All arrival times are **distinct**.

Return _the **chair number** that the friend numbered_ `targetFriend` _will sit on_.

**Example 1:**

**Input:** times = \[\[1,4\],\[2,3\],\[4,6\]\], targetFriend = 1
**Output:** 1
**Explanation:** 
- Friend 0 arrives at time 1 and sits on chair 0.
- Friend 1 arrives at time 2 and sits on chair 1.
- Friend 1 leaves at time 3 and chair 1 becomes empty.
- Friend 0 leaves at time 4 and chair 0 becomes empty.
- Friend 2 arrives at time 4 and sits on chair 0.
Since friend 1 sat on chair 1, we return 1.

**Example 2:**

**Input:** times = \[\[3,10\],\[1,5\],\[2,6\]\], targetFriend = 0
**Output:** 2
**Explanation:** 
- Friend 1 arrives at time 1 and sits on chair 0.
- Friend 2 arrives at time 2 and sits on chair 1.
- Friend 0 arrives at time 3 and sits on chair 2.
- Friend 1 leaves at time 5 and chair 0 becomes empty.
- Friend 2 leaves at time 6 and chair 1 becomes empty.
- Friend 0 leaves at time 10 and chair 2 becomes empty.
Since friend 0 sat on chair 2, we return 2.

**Constraints:**

*   `n == times.length`
*   `2 <= n <= 104`
*   `times[i].length == 2`
*   `1 <= arrivali < leavingi <= 105`
*   `0 <= targetFriend <= n - 1`
*   Each `arrivali` time is **distinct**.
Describe the Painting

There is a long and thin painting that can be represented by a number line. The painting was painted with multiple overlapping segments where each segment was painted with a **unique** color. You are given a 2D integer array `segments`, where `segments[i] = [starti, endi, colori]` represents the **half-closed segment** `[starti, endi)` with `colori` as the color.

The colors in the overlapping segments of the painting were **mixed** when it was painted. When two or more colors mix, they form a new color that can be represented as a **set** of mixed colors.

*   For example, if colors `2`, `4`, and `6` are mixed, then the resulting mixed color is `{2,4,6}`.

For the sake of simplicity, you should only output the **sum** of the elements in the set rather than the full set.

You want to **describe** the painting with the **minimum** number of non-overlapping **half-closed segments** of these mixed colors. These segments can be represented by the 2D array `painting` where `painting[j] = [leftj, rightj, mixj]` describes a **half-closed segment** `[leftj, rightj)` with the mixed color **sum** of `mixj`.

*   For example, the painting created with `segments = [[1,4,5],[1,7,7]]` can be described by `painting = [[1,4,12],[4,7,7]]` because:
    *   `[1,4)` is colored `{5,7}` (with a sum of `12`) from both the first and second segments.
    *   `[4,7)` is colored `{7}` from only the second segment.

Return _the 2D array_ `painting` _describing the finished painting (excluding any parts that are **not** painted). You may return the segments in **any order**_.

A **half-closed segment** `[a, b)` is the section of the number line between points `a` and `b` **including** point `a` and **not including** point `b`.

**Example 1:**

**Input:** segments = \[\[1,4,5\],\[4,7,7\],\[1,7,9\]\]
**Output:** \[\[1,4,14\],\[4,7,16\]\]
**Explanation:** The painting can be described as follows:
- \[1,4) is colored {5,9} (with a sum of 14) from the first and third segments.
- \[4,7) is colored {7,9} (with a sum of 16) from the second and third segments.

**Example 2:**

**Input:** segments = \[\[1,7,9\],\[6,8,15\],\[8,10,7\]\]
**Output:** \[\[1,6,9\],\[6,7,24\],\[7,8,15\],\[8,10,7\]\]
**Explanation:** The painting can be described as follows:
- \[1,6) is colored 9 from the first segment.
- \[6,7) is colored {9,15} (with a sum of 24) from the first and second segments.
- \[7,8) is colored 15 from the second segment.
- \[8,10) is colored 7 from the third segment.

**Example 3:**

**Input:** segments = \[\[1,4,5\],\[1,4,7\],\[4,7,1\],\[4,7,11\]\]
**Output:** \[\[1,4,12\],\[4,7,12\]\]
**Explanation:** The painting can be described as follows:
- \[1,4) is colored {5,7} (with a sum of 12) from the first and second segments.
- \[4,7) is colored {1,11} (with a sum of 12) from the third and fourth segments.
Note that returning a single segment \[1,7) is incorrect because the mixed color sets are different.

**Constraints:**

*   `1 <= segments.length <= 2 * 104`
*   `segments[i].length == 3`
*   `1 <= starti < endi <= 105`
*   `1 <= colori <= 109`
*   Each `colori` is distinct.
Number of Visible People in a Queue

There are `n` people standing in a queue, and they numbered from `0` to `n - 1` in **left to right** order. You are given an array `heights` of **distinct** integers where `heights[i]` represents the height of the `ith` person.

A person can **see** another person to their right in the queue if everybody in between is **shorter** than both of them. More formally, the `ith` person can see the `jth` person if `i < j` and `min(heights[i], heights[j]) > max(heights[i+1], heights[i+2], ..., heights[j-1])`.

Return _an array_ `answer` _of length_ `n` _where_ `answer[i]` _is the **number of people** the_ `ith` _person can **see** to their right in the queue_.

**Example 1:**

**Input:** heights = \[10,6,8,5,11,9\]
**Output:** \[3,1,2,1,1,0\]
**Explanation:**
Person 0 can see person 1, 2, and 4.
Person 1 can see person 2.
Person 2 can see person 3 and 4.
Person 3 can see person 4.
Person 4 can see person 5.
Person 5 can see no one since nobody is to the right of them.

**Example 2:**

**Input:** heights = \[5,1,2,3,10\]
**Output:** \[4,1,1,1,0\]

**Constraints:**

*   `n == heights.length`
*   `1 <= n <= 105`
*   `1 <= heights[i] <= 105`
*   All the values of `heights` are **unique**.
Sum of Digits of String After Convert

You are given a string `s` consisting of lowercase English letters, and an integer `k`.

First, **convert** `s` into an integer by replacing each letter with its position in the alphabet (i.e., replace `'a'` with `1`, `'b'` with `2`, ..., `'z'` with `26`). Then, **transform** the integer by replacing it with the **sum of its digits**. Repeat the **transform** operation `k` **times** in total.

For example, if `s = "zbax "` and `k = 2`, then the resulting integer would be `8` by the following operations:

*   **Convert**: `"zbax " ➝ "(26)(2)(1)(24) " ➝ "262124 " ➝ 262124`
*   **Transform #1**: `262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17`
*   **Transform #2**: `17 ➝ 1 + 7 ➝ 8`

Return _the resulting integer after performing the operations described above_.

**Example 1:**

**Input:** s =  "iiii ", k = 1
**Output:** 36
**Explanation:** The operations are as follows:
- Convert:  "iiii " ➝  "(9)(9)(9)(9) " ➝  "9999 " ➝ 9999
- Transform #1: 9999 ➝ 9 + 9 + 9 + 9 ➝ 36
Thus the resulting integer is 36.

**Example 2:**

**Input:** s =  "leetcode ", k = 2
**Output:** 6
**Explanation:** The operations are as follows:
- Convert:  "leetcode " ➝  "(12)(5)(5)(20)(3)(15)(4)(5) " ➝  "12552031545 " ➝ 12552031545
- Transform #1: 12552031545 ➝ 1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 ➝ 33
- Transform #2: 33 ➝ 3 + 3 ➝ 6
Thus the resulting integer is 6.

**Example 3:**

**Input:** s =  "zbax ", k = 2
**Output:** 8

**Constraints:**

*   `1 <= s.length <= 100`
*   `1 <= k <= 10`
*   `s` consists of lowercase English letters.
Largest Number After Mutating Substring

You are given a string `num`, which represents a large integer. You are also given a **0-indexed** integer array `change` of length `10` that maps each digit `0-9` to another digit. More formally, digit `d` maps to digit `change[d]`.

You may **choose** to **mutate a single substring** of `num`. To mutate a substring, replace each digit `num[i]` with the digit it maps to in `change` (i.e. replace `num[i]` with `change[num[i]]`).

Return _a string representing the **largest** possible integer after **mutating** (or choosing not to) a **single substring** of_ `num`.

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

**Example 1:**

**Input:** num =  "132 ", change = \[9,8,5,0,3,6,4,2,6,8\]
**Output:**  "832 "
**Explanation:** Replace the substring  "1 ":
- 1 maps to change\[1\] = 8.
Thus,  "132 " becomes  "832 ".
 "832 " is the largest number that can be created, so return it.

**Example 2:**

**Input:** num =  "021 ", change = \[9,4,3,5,7,2,1,9,0,6\]
**Output:**  "934 "
**Explanation:** Replace the substring  "021 ":
- 0 maps to change\[0\] = 9.
- 2 maps to change\[2\] = 3.
- 1 maps to change\[1\] = 4.
Thus,  "021 " becomes  "934 ".
 "934 " is the largest number that can be created, so return it.

**Example 3:**

**Input:** num =  "5 ", change = \[1,4,7,5,3,2,5,6,9,4\]
**Output:**  "5 "
**Explanation:**  "5 " is already the largest number that can be created, so return it.

**Constraints:**

*   `1 <= num.length <= 105`
*   `num` consists of only digits `0-9`.
*   `change.length == 10`
*   `0 <= change[d] <= 9`