bowang0911/leetcode huggingface dataset:
Maximum Product of the Length of Two Palindromic Subsequences

Given a string `s`, find two **disjoint palindromic subsequences** of `s` such that the **product** of their lengths is **maximized**. The two subsequences are **disjoint** if they do not both pick a character at the same index.

Return _the **maximum** possible **product** of the lengths of the two palindromic subsequences_.

A **subsequence** is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. A string is **palindromic** if it reads the same forward and backward.

**Example 1:**

**Input:** s =  "leetcodecom "
**Output:** 9
**Explanation**: An optimal solution is to choose  "ete " for the 1st subsequence and  "cdc " for the 2nd subsequence.
The product of their lengths is: 3 \* 3 = 9.

**Example 2:**

**Input:** s =  "bb "
**Output:** 1
**Explanation**: An optimal solution is to choose  "b " (the first character) for the 1st subsequence and  "b " (the second character) for the 2nd subsequence.
The product of their lengths is: 1 \* 1 = 1.

**Example 3:**

**Input:** s =  "accbcaxxcxx "
**Output:** 25
**Explanation**: An optimal solution is to choose  "accca " for the 1st subsequence and  "xxcxx " for the 2nd subsequence.
The product of their lengths is: 5 \* 5 = 25.

**Constraints:**

*   `2 <= s.length <= 12`
*   `s` consists of lowercase English letters only.
Smallest Missing Genetic Value in Each Subtree

There is a **family tree** rooted at `0` consisting of `n` nodes numbered `0` to `n - 1`. You are given a **0-indexed** integer array `parents`, where `parents[i]` is the parent for node `i`. Since node `0` is the **root**, `parents[0] == -1`.

There are `105` genetic values, each represented by an integer in the **inclusive** range `[1, 105]`. You are given a **0-indexed** integer array `nums`, where `nums[i]` is a **distinct** genetic value for node `i`.

Return _an array_ `ans` _of length_ `n` _where_ `ans[i]` _is_ _the **smallest** genetic value that is **missing** from the subtree rooted at node_ `i`.

The **subtree** rooted at a node `x` contains node `x` and all of its **descendant** nodes.

**Example 1:**

**Input:** parents = \[-1,0,0,2\], nums = \[1,2,3,4\]
**Output:** \[5,1,1,1\]
**Explanation:** The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes \[0,1,2,3\] with values \[1,2,3,4\]. 5 is the smallest missing value.
- 1: The subtree contains only node 1 with value 2. 1 is the smallest missing value.
- 2: The subtree contains nodes \[2,3\] with values \[3,4\]. 1 is the smallest missing value.
- 3: The subtree contains only node 3 with value 4. 1 is the smallest missing value.

**Example 2:**

**Input:** parents = \[-1,0,1,0,3,3\], nums = \[5,4,6,2,1,3\]
**Output:** \[7,1,1,4,2,1\]
**Explanation:** The answer for each subtree is calculated as follows:
- 0: The subtree contains nodes \[0,1,2,3,4,5\] with values \[5,4,6,2,1,3\]. 7 is the smallest missing value.
- 1: The subtree contains nodes \[1,2\] with values \[4,6\]. 1 is the smallest missing value.
- 2: The subtree contains only node 2 with value 6. 1 is the smallest missing value.
- 3: The subtree contains nodes \[3,4,5\] with values \[2,1,3\]. 4 is the smallest missing value.
- 4: The subtree contains only node 4 with value 1. 2 is the smallest missing value.
- 5: The subtree contains only node 5 with value 3. 1 is the smallest missing value.

**Example 3:**

**Input:** parents = \[-1,2,3,0,2,4,1\], nums = \[2,3,4,5,6,7,8\]
**Output:** \[1,1,1,1,1,1,1\]
**Explanation:** The value 1 is missing from all the subtrees.

**Constraints:**

*   `n == parents.length == nums.length`
*   `2 <= n <= 105`
*   `0 <= parents[i] <= n - 1` for `i != 0`
*   `parents[0] == -1`
*   `parents` represents a valid tree.
*   `1 <= nums[i] <= 105`
*   Each `nums[i]` is distinct.
Subtree Removal Game with Fibonacci Tree

A **Fibonacci** tree is a binary tree created using the order function `order(n)`:

*   `order(0)` is the empty tree.
*   `order(1)` is a binary tree with only **one node**.
*   `order(n)` is a binary tree that consists of a root node with the left subtree as `order(n - 2)` and the right subtree as `order(n - 1)`.

Alice and Bob are playing a game with a **Fibonacci** tree with Alice staring first. On each turn, a player selects a node and removes that node **and** its subtree. The player that is forced to delete `root` loses.

Given the integer `n`, return `true` if Alice wins the game or `false` if Bob wins, assuming both players play optimally.

A subtree of a binary tree `tree` is a tree that consists of a node in `tree` and all of this node's descendants. The tree `tree` could also be considered as a subtree of itself.

**Example 1:**  

**Input:** n = 3
**Output:** true
**Explanation:**
Alice takes the node 1 in the right subtree.
Bob takes either the 1 in the left subtree or the 2 in the right subtree.
Alice takes whichever node Bob doesn't take.
Bob is forced to take the root node 3, so Bob will lose.
Return true because Alice wins.

**Example 2:**  

**Input:** n = 1
**Output:** false
**Explanation:**
Alice is forced to take the root node 1, so Alice will lose.
Return false because Alice loses.

**Example 3:**  

**Input:** n = 2
**Output:** true
**Explanation:**
Alice takes the node 1.
Bob is forced to take the root node 2, so Bob will lose.
Return true because Alice wins.

**Constraints:**

*   `1 <= n <= 100`
Count Number of Pairs With Absolute Difference K

Given an integer array `nums` and an integer `k`, return _the number of pairs_ `(i, j)` _where_ `i < j` _such that_ `|nums[i] - nums[j]| == k`.

The value of `|x|` is defined as:

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

**Example 1:**

**Input:** nums = \[1,2,2,1\], k = 1
**Output:** 4
**Explanation:** The pairs with an absolute difference of 1 are:
- \[**1**,**2**,2,1\]
- \[**1**,2,**2**,1\]
- \[1,**2**,2,**1**\]
- \[1,2,**2**,**1**\]

**Example 2:**

**Input:** nums = \[1,3\], k = 3
**Output:** 0
**Explanation:** There are no pairs with an absolute difference of 3.

**Example 3:**

**Input:** nums = \[3,2,1,5,4\], k = 2
**Output:** 3
**Explanation:** The pairs with an absolute difference of 2 are:
- \[**3**,2,**1**,5,4\]
- \[**3**,2,1,**5**,4\]
- \[3,**2**,1,5,**4**\]

**Constraints:**

*   `1 <= nums.length <= 200`
*   `1 <= nums[i] <= 100`
*   `1 <= k <= 99`
Find Original Array From Doubled Array

An integer array `original` is transformed into a **doubled** array `changed` by appending **twice the value** of every element in `original`, and then randomly **shuffling** the resulting array.

Given an array `changed`, return `original` _if_ `changed` _is a **doubled** array. If_ `changed` _is not a **doubled** array, return an empty array. The elements in_ `original` _may be returned in **any** order_.

**Example 1:**

**Input:** changed = \[1,3,4,2,6,8\]
**Output:** \[1,3,4\]
**Explanation:** One possible original array could be \[1,3,4\]:
- Twice the value of 1 is 1 \* 2 = 2.
- Twice the value of 3 is 3 \* 2 = 6.
- Twice the value of 4 is 4 \* 2 = 8.
Other original arrays could be \[4,3,1\] or \[3,1,4\].

**Example 2:**

**Input:** changed = \[6,3,0,1\]
**Output:** \[\]
**Explanation:** changed is not a doubled array.

**Example 3:**

**Input:** changed = \[1\]
**Output:** \[\]
**Explanation:** changed is not a doubled array.

**Constraints:**

*   `1 <= changed.length <= 105`
*   `0 <= changed[i] <= 105`
Maximum Earnings From Taxi

There are `n` points on a road you are driving your taxi on. The `n` points on the road are labeled from `1` to `n` in the direction you are going, and you want to drive from point `1` to point `n` to make money by picking up passengers. You cannot change the direction of the taxi.

The passengers are represented by a **0-indexed** 2D integer array `rides`, where `rides[i] = [starti, endi, tipi]` denotes the `ith` passenger requesting a ride from point `starti` to point `endi` who is willing to give a `tipi` dollar tip.

For **each** passenger `i` you pick up, you **earn** `endi - starti + tipi` dollars. You may only drive **at most one** passenger at a time.

Given `n` and `rides`, return _the **maximum** number of dollars you can earn by picking up the passengers optimally._

**Note:** You may drop off a passenger and pick up a different passenger at the same point.

**Example 1:**

**Input:** n = 5, rides = \[\[2,5,4\],\[1,5,1\]\]
**Output:** 7
**Explanation:** We can pick up passenger 0 to earn 5 - 2 + 4 = 7 dollars.

**Example 2:**

**Input:** n = 20, rides = \[\[1,6,1\],\[3,10,2\],\[10,12,3\],\[11,12,2\],\[12,15,2\],\[13,18,1\]\]
**Output:** 20
**Explanation:** We will pick up the following passengers:
- Drive passenger 1 from point 3 to point 10 for a profit of 10 - 3 + 2 = 9 dollars.
- Drive passenger 2 from point 10 to point 12 for a profit of 12 - 10 + 3 = 5 dollars.
- Drive passenger 5 from point 13 to point 18 for a profit of 18 - 13 + 1 = 6 dollars.
We earn 9 + 5 + 6 = 20 dollars in total.

**Constraints:**

*   `1 <= n <= 105`
*   `1 <= rides.length <= 3 * 104`
*   `rides[i].length == 3`
*   `1 <= starti < endi <= n`
*   `1 <= tipi <= 105`
Minimum Number of Operations to Make Array Continuous

You are given an integer array `nums`. In one operation, you can replace **any** element in `nums` with **any** integer.

`nums` is considered **continuous** if both of the following conditions are fulfilled:

*   All elements in `nums` are **unique**.
*   The difference between the **maximum** element and the **minimum** element in `nums` equals `nums.length - 1`.

For example, `nums = [4, 2, 5, 3]` is **continuous**, but `nums = [1, 2, 3, 5, 6]` is **not continuous**.

Return _the **minimum** number of operations to make_ `nums` **_continuous_**.

**Example 1:**

**Input:** nums = \[4,2,5,3\]
**Output:** 0
**Explanation:** nums is already continuous.

**Example 2:**

**Input:** nums = \[1,2,3,5,6\]
**Output:** 1
**Explanation:** One possible solution is to change the last element to 4.
The resulting array is \[1,2,3,5,4\], which is continuous.

**Example 3:**

**Input:** nums = \[1,10,100,1000\]
**Output:** 3
**Explanation:** One possible solution is to:
- Change the second element to 2.
- Change the third element to 3.
- Change the fourth element to 4.
The resulting array is \[1,2,3,4\], which is continuous.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `1 <= nums[i] <= 109`
Final Value of Variable After Performing Operations

There is a programming language with only **four** operations and **one** variable `X`:

*   `++X` and `X++` **increments** the value of the variable `X` by `1`.
*   `--X` and `X--` **decrements** the value of the variable `X` by `1`.

Initially, the value of `X` is `0`.

Given an array of strings `operations` containing a list of operations, return _the **final** value of_ `X` _after performing all the operations_.

**Example 1:**

**Input:** operations = \[ "--X ", "X++ ", "X++ "\]
**Output:** 1
**Explanation:** The operations are performed as follows:
Initially, X = 0.
--X: X is decremented by 1, X =  0 - 1 = -1.
X++: X is incremented by 1, X = -1 + 1 =  0.
X++: X is incremented by 1, X =  0 + 1 =  1.

**Example 2:**

**Input:** operations = \[ "++X ", "++X ", "X++ "\]
**Output:** 3
**Explanation:** The operations are performed as follows:
Initially, X = 0.
++X: X is incremented by 1, X = 0 + 1 = 1.
++X: X is incremented by 1, X = 1 + 1 = 2.
X++: X is incremented by 1, X = 2 + 1 = 3.

**Example 3:**

**Input:** operations = \[ "X++ ", "++X ", "--X ", "X-- "\]
**Output:** 0
**Explanation:** The operations are performed as follows:
Initially, X = 0.
X++: X is incremented by 1, X = 0 + 1 = 1.
++X: X is incremented by 1, X = 1 + 1 = 2.
--X: X is decremented by 1, X = 2 - 1 = 1.
X--: X is decremented by 1, X = 1 - 1 = 0.

**Constraints:**

*   `1 <= operations.length <= 100`
*   `operations[i]` will be either `"++X "`, `"X++ "`, `"--X "`, or `"X-- "`.
Sum of Beauty in the Array

You are given a **0-indexed** integer array `nums`. For each index `i` (`1 <= i <= nums.length - 2`) the **beauty** of `nums[i]` equals:

*   `2`, if `nums[j] < nums[i] < nums[k]`, for **all** `0 <= j < i` and for **all** `i < k <= nums.length - 1`.
*   `1`, if `nums[i - 1] < nums[i] < nums[i + 1]`, and the previous condition is not satisfied.
*   `0`, if none of the previous conditions holds.

Return _the **sum of beauty** of all_ `nums[i]` _where_ `1 <= i <= nums.length - 2`.

**Example 1:**

**Input:** nums = \[1,2,3\]
**Output:** 2
**Explanation:** For each index i in the range 1 <= i <= 1:
- The beauty of nums\[1\] equals 2.

**Example 2:**

**Input:** nums = \[2,4,6,4\]
**Output:** 1
**Explanation:** For each index i in the range 1 <= i <= 2:
- The beauty of nums\[1\] equals 1.
- The beauty of nums\[2\] equals 0.

**Example 3:**

**Input:** nums = \[3,2,1\]
**Output:** 0
**Explanation:** For each index i in the range 1 <= i <= 1:
- The beauty of nums\[1\] equals 0.

**Constraints:**

*   `3 <= nums.length <= 105`
*   `1 <= nums[i] <= 105`
Detect Squares

You are given a stream of points on the X-Y plane. Design an algorithm that:

*   **Adds** new points from the stream into a data structure. **Duplicate** points are allowed and should be treated as different points.
*   Given a query point, **counts** the number of ways to choose three points from the data structure such that the three points and the query point form an **axis-aligned square** with **positive area**.

An **axis-aligned square** is a square whose edges are all the same length and are either parallel or perpendicular to the x-axis and y-axis.

Implement the `DetectSquares` class:

*   `DetectSquares()` Initializes the object with an empty data structure.
*   `void add(int[] point)` Adds a new point `point = [x, y]` to the data structure.
*   `int count(int[] point)` Counts the number of ways to form **axis-aligned squares** with point `point = [x, y]` as described above.

**Example 1:**

**Input**
\[ "DetectSquares ",  "add ",  "add ",  "add ",  "count ",  "count ",  "add ",  "count "\]
\[\[\], \[\[3, 10\]\], \[\[11, 2\]\], \[\[3, 2\]\], \[\[11, 10\]\], \[\[14, 8\]\], \[\[11, 2\]\], \[\[11, 10\]\]\]
**Output**
\[null, null, null, null, 1, 0, null, 2\]

**Explanation**
DetectSquares detectSquares = new DetectSquares();
detectSquares.add(\[3, 10\]);
detectSquares.add(\[11, 2\]);
detectSquares.add(\[3, 2\]);
detectSquares.count(\[11, 10\]); // return 1. You can choose:
                               //   - The first, second, and third points
detectSquares.count(\[14, 8\]);  // return 0. The query point cannot form a square with any points in the data structure.
detectSquares.add(\[11, 2\]);    // Adding duplicate points is allowed.
detectSquares.count(\[11, 10\]); // return 2. You can choose:
                               //   - The first, second, and third points
                               //   - The first, third, and fourth points

**Constraints:**

*   `point.length == 2`
*   `0 <= x, y <= 1000`
*   At most `3000` calls **in total** will be made to `add` and `count`.
Longest Subsequence Repeated k Times

You are given a string `s` of length `n`, and an integer `k`. You are tasked to find the **longest subsequence repeated** `k` times in string `s`.

A **subsequence** is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

A subsequence `seq` is **repeated** `k` times in the string `s` if `seq * k` is a subsequence of `s`, where `seq * k` represents a string constructed by concatenating `seq` `k` times.

*   For example, `"bba "` is repeated `2` times in the string `"bababcba "`, because the string `"bbabba "`, constructed by concatenating `"bba "` `2` times, is a subsequence of the string `"**b**a**bab**c**ba** "`.

Return _the **longest subsequence repeated**_ `k` _times in string_ `s`_. If multiple such subsequences are found, return the **lexicographically largest** one. If there is no such subsequence, return an **empty** string_.

**Example 1:**

**Input:** s =  "letsleetcode ", k = 2
**Output:**  "let "
**Explanation:** There are two longest subsequences repeated 2 times:  "let " and  "ete ".
 "let " is the lexicographically largest one.

**Example 2:**

**Input:** s =  "bb ", k = 2
**Output:**  "b "
**Explanation:** The longest subsequence repeated 2 times is  "b ".

**Example 3:**

**Input:** s =  "ab ", k = 2
**Output:**  " "
**Explanation:** There is no subsequence repeated 2 times. Empty string is returned.

**Constraints:**

*   `n == s.length`
*   `2 <= n, k <= 2000`
*   `2 <= n < k * 8`
*   `s` consists of lowercase English letters.
Maximum Difference Between Increasing Elements

Given a **0-indexed** integer array `nums` of size `n`, find the **maximum difference** between `nums[i]` and `nums[j]` (i.e., `nums[j] - nums[i]`), such that `0 <= i < j < n` and `nums[i] < nums[j]`.

Return _the **maximum difference**._ If no such `i` and `j` exists, return `-1`.

**Example 1:**

**Input:** nums = \[7,**1**,**5**,4\]
**Output:** 4
**Explanation:**
The maximum difference occurs with i = 1 and j = 2, nums\[j\] - nums\[i\] = 5 - 1 = 4.
Note that with i = 1 and j = 0, the difference nums\[j\] - nums\[i\] = 7 - 1 = 6, but i > j, so it is not valid.

**Example 2:**

**Input:** nums = \[9,4,3,2\]
**Output:** -1
**Explanation:**
There is no i and j such that i < j and nums\[i\] < nums\[j\].

**Example 3:**

**Input:** nums = \[**1**,5,2,**10**\]
**Output:** 9
**Explanation:**
The maximum difference occurs with i = 0 and j = 3, nums\[j\] - nums\[i\] = 10 - 1 = 9.

**Constraints:**

*   `n == nums.length`
*   `2 <= n <= 1000`
*   `1 <= nums[i] <= 109`
Grid Game

You are given a **0-indexed** 2D array `grid` of size `2 x n`, where `grid[r][c]` represents the number of points at position `(r, c)` on the matrix. Two robots are playing a game on this matrix.

Both robots initially start at `(0, 0)` and want to reach `(1, n-1)`. Each robot may only move to the **right** (`(r, c)` to `(r, c + 1)`) or **down** (`(r, c)` to `(r + 1, c)`).

At the start of the game, the **first** robot moves from `(0, 0)` to `(1, n-1)`, collecting all the points from the cells on its path. For all cells `(r, c)` traversed on the path, `grid[r][c]` is set to `0`. Then, the **second** robot moves from `(0, 0)` to `(1, n-1)`, collecting the points on its path. Note that their paths may intersect with one another.

The **first** robot wants to **minimize** the number of points collected by the **second** robot. In contrast, the **second** robot wants to **maximize** the number of points it collects. If both robots play **optimally**, return _the **number of points** collected by the **second** robot._

**Example 1:**

**Input:** grid = \[\[2,5,4\],\[1,5,1\]\]
**Output:** 4
**Explanation:** The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 0 + 4 + 0 = 4 points.

**Example 2:**

**Input:** grid = \[\[3,3,1\],\[8,5,2\]\]
**Output:** 4
**Explanation:** The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 3 + 1 + 0 = 4 points.

**Example 3:**

**Input:** grid = \[\[1,3,1,15\],\[1,3,3,1\]\]
**Output:** 7
**Explanation:** The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 1 + 3 + 3 + 0 = 7 points.

**Constraints:**

*   `grid.length == 2`
*   `n == grid[r].length`
*   `1 <= n <= 5 * 104`
*   `1 <= grid[r][c] <= 105`
Check if Word Can Be Placed In Crossword

You are given an `m x n` matrix `board`, representing the **current** state of a crossword puzzle. The crossword contains lowercase English letters (from solved words), `' '` to represent any **empty** cells, and `'#'` to represent any **blocked** cells.

A word can be placed **horizontally** (left to right **or** right to left) or **vertically** (top to bottom **or** bottom to top) in the board if:

*   It does not occupy a cell containing the character `'#'`.
*   The cell each letter is placed in must either be `' '` (empty) or **match** the letter already on the `board`.
*   There must not be any empty cells `' '` or other lowercase letters **directly left or right** of the word if the word was placed **horizontally**.
*   There must not be any empty cells `' '` or other lowercase letters **directly above or below** the word if the word was placed **vertically**.

Given a string `word`, return `true` _if_ `word` _can be placed in_ `board`_, or_ `false` _**otherwise**_.

**Example 1:**

**Input:** board = \[\[ "# ",  "  ",  "# "\], \[ "  ",  "  ",  "# "\], \[ "# ",  "c ",  "  "\]\], word =  "abc "
**Output:** true
**Explanation:** The word  "abc " can be placed as shown above (top to bottom).

**Example 2:**

**Input:** board = \[\[ "  ",  "# ",  "a "\], \[ "  ",  "# ",  "c "\], \[ "  ",  "# ",  "a "\]\], word =  "ac "
**Output:** false
**Explanation:** It is impossible to place the word because there will always be a space/letter above or below it.

**Example 3:**

**Input:** board = \[\[ "# ",  "  ",  "# "\], \[ "  ",  "  ",  "# "\], \[ "# ",  "  ",  "c "\]\], word =  "ca "
**Output:** true
**Explanation:** The word  "ca " can be placed as shown above (right to left). 

**Constraints:**

*   `m == board.length`
*   `n == board[i].length`
*   `1 <= m * n <= 2 * 105`
*   `board[i][j]` will be `' '`, `'#'`, or a lowercase English letter.
*   `1 <= word.length <= max(m, n)`
*   `word` will contain only lowercase English letters.