bowang0911/leetcode huggingface dataset:
Design Most Recently Used Queue

Design a queue-like data structure that moves the most recently used element to the end of the queue.

Implement the `MRUQueue` class:

*   `MRUQueue(int n)` constructs the `MRUQueue` with `n` elements: `[1,2,3,...,n]`.
*   `int fetch(int k)` moves the `kth` element **(1-indexed)** to the end of the queue and returns it.

**Example 1:**

**Input:**
\[ "MRUQueue ",  "fetch ",  "fetch ",  "fetch ",  "fetch "\]
\[\[8\], \[3\], \[5\], \[2\], \[8\]\]
**Output:**
\[null, 3, 6, 2, 2\]

**Explanation:**
MRUQueue mRUQueue = new MRUQueue(8); // Initializes the queue to \[1,2,3,4,5,6,7,8\].
mRUQueue.fetch(3); // Moves the 3rd element (3) to the end of the queue to become \[1,2,4,5,6,7,8,3\] and returns it.
mRUQueue.fetch(5); // Moves the 5th element (6) to the end of the queue to become \[1,2,4,5,7,8,3,6\] and returns it.
mRUQueue.fetch(2); // Moves the 2nd element (2) to the end of the queue to become \[1,4,5,7,8,3,6,2\] and returns it.
mRUQueue.fetch(8); // The 8th element (2) is already at the end of the queue so just return it.

**Constraints:**

*   `1 <= n <= 2000`
*   `1 <= k <= n`
*   At most `2000` calls will be made to `fetch`.

**Follow up:** Finding an `O(n)` algorithm per `fetch` is a bit easy. Can you find an algorithm with a better complexity for each `fetch` call?
Minimum Changes To Make Alternating Binary String

You are given a string `s` consisting only of the characters `'0'` and `'1'`. In one operation, you can change any `'0'` to `'1'` or vice versa.

The string is called alternating if no two adjacent characters are equal. For example, the string `"010 "` is alternating, while the string `"0100 "` is not.

Return _the **minimum** number of operations needed to make_ `s` _alternating_.

**Example 1:**

**Input:** s =  "0100 "
**Output:** 1
**Explanation:** If you change the last character to '1', s will be  "0101 ", which is alternating.

**Example 2:**

**Input:** s =  "10 "
**Output:** 0
**Explanation:** s is already alternating.

**Example 3:**

**Input:** s =  "1111 "
**Output:** 2
**Explanation:** You need two operations to reach  "0101 " or  "1010 ".

**Constraints:**

*   `1 <= s.length <= 104`
*   `s[i]` is either `'0'` or `'1'`.
Count Number of Homogenous Substrings

Given a string `s`, return _the number of **homogenous** substrings of_ `s`_._ Since the answer may be too large, return it **modulo** `109 + 7`.

A string is **homogenous** if all the characters of the string are the same.

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

**Example 1:**

**Input:** s =  "abbcccaa "
**Output:** 13
**Explanation:** The homogenous substrings are listed as below:
 "a "   appears 3 times.
 "aa "  appears 1 time.
 "b "   appears 2 times.
 "bb "  appears 1 time.
 "c "   appears 3 times.
 "cc "  appears 2 times.
 "ccc " appears 1 time.
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13.

**Example 2:**

**Input:** s =  "xy "
**Output:** 2
**Explanation:** The homogenous substrings are  "x " and  "y ".

**Example 3:**

**Input:** s =  "zzzzz "
**Output:** 15

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists of lowercase letters.
Minimum Limit of Balls in a Bag

You are given an integer array `nums` where the `ith` bag contains `nums[i]` balls. You are also given an integer `maxOperations`.

You can perform the following operation at most `maxOperations` times:

*   Take any bag of balls and divide it into two new bags with a **positive** number of balls.
    *   For example, a bag of `5` balls can become two new bags of `1` and `4` balls, or two new bags of `2` and `3` balls.

Your penalty is the **maximum** number of balls in a bag. You want to **minimize** your penalty after the operations.

Return _the minimum possible penalty after performing the operations_.

**Example 1:**

**Input:** nums = \[9\], maxOperations = 2
**Output:** 3
**Explanation:** 
- Divide the bag with 9 balls into two bags of sizes 6 and 3. \[**9**\] -> \[6,3\].
- Divide the bag with 6 balls into two bags of sizes 3 and 3. \[**6**,3\] -> \[3,3,3\].
The bag with the most number of balls has 3 balls, so your penalty is 3 and you should return 3.

**Example 2:**

**Input:** nums = \[2,4,8,2\], maxOperations = 4
**Output:** 2
**Explanation:**
- Divide the bag with 8 balls into two bags of sizes 4 and 4. \[2,4,**8**,2\] -> \[2,4,4,4,2\].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. \[2,**4**,4,4,2\] -> \[2,2,2,4,4,2\].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. \[2,2,2,**4**,4,2\] -> \[2,2,2,2,2,4,2\].
- Divide the bag with 4 balls into two bags of sizes 2 and 2. \[2,2,2,2,2,**4**,2\] -> \[2,2,2,2,2,2,2,2\].
The bag with the most number of balls has 2 balls, so your penalty is 2, and you should return 2.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `1 <= maxOperations, nums[i] <= 109`
Minimum Degree of a Connected Trio in a Graph

You are given an undirected graph. You are given an integer `n` which is the number of nodes in the graph and an array `edges`, where each `edges[i] = [ui, vi]` indicates that there is an undirected edge between `ui` and `vi`.

A **connected trio** is a set of **three** nodes where there is an edge between **every** pair of them.

The **degree of a connected trio** is the number of edges where one endpoint is in the trio, and the other is not.

Return _the **minimum** degree of a connected trio in the graph, or_ `-1` _if the graph has no connected trios._

**Example 1:**

**Input:** n = 6, edges = \[\[1,2\],\[1,3\],\[3,2\],\[4,1\],\[5,2\],\[3,6\]\]
**Output:** 3
**Explanation:** There is exactly one trio, which is \[1,2,3\]. The edges that form its degree are bolded in the figure above.

**Example 2:**

**Input:** n = 7, edges = \[\[1,3\],\[4,1\],\[4,3\],\[2,5\],\[5,6\],\[6,7\],\[7,5\],\[2,6\]\]
**Output:** 0
**Explanation:** There are exactly three trios:
1) \[1,4,3\] with degree 0.
2) \[2,5,6\] with degree 2.
3) \[5,6,7\] with degree 2.

**Constraints:**

*   `2 <= n <= 400`
*   `edges[i].length == 2`
*   `1 <= edges.length <= n * (n-1) / 2`
*   `1 <= ui, vi <= n`
*   `ui != vi`
*   There are no repeated edges.
Buildings With an Ocean View

There are `n` buildings in a line. You are given an integer array `heights` of size `n` that represents the heights of the buildings in the line.

The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a **smaller** height.

Return a list of indices **(0-indexed)** of buildings that have an ocean view, sorted in increasing order.

**Example 1:**

**Input:** heights = \[4,2,3,1\]
**Output:** \[0,2,3\]
**Explanation:** Building 1 (0-indexed) does not have an ocean view because building 2 is taller.

**Example 2:**

**Input:** heights = \[4,3,2,1\]
**Output:** \[0,1,2,3\]
**Explanation:** All the buildings have an ocean view.

**Example 3:**

**Input:** heights = \[1,3,2,4\]
**Output:** \[3\]
**Explanation:** Only building 3 has an ocean view.

**Constraints:**

*   `1 <= heights.length <= 105`
*   `1 <= heights[i] <= 109`
Longest Nice Substring

A string `s` is **nice** if, for every letter of the alphabet that `s` contains, it appears **both** in uppercase and lowercase. For example, `"abABB "` is nice because `'A'` and `'a'` appear, and `'B'` and `'b'` appear. However, `"abA "` is not because `'b'` appears, but `'B'` does not.

Given a string `s`, return _the longest **substring** of `s` that is **nice**. If there are multiple, return the substring of the **earliest** occurrence. If there are none, return an empty string_.

**Example 1:**

**Input:** s =  "YazaAay "
**Output:**  "aAa "
**Explanation: ** "aAa " is a nice string because 'A/a' is the only letter of the alphabet in s, and both 'A' and 'a' appear.
 "aAa " is the longest nice substring.

**Example 2:**

**Input:** s =  "Bb "
**Output:**  "Bb "
**Explanation:**  "Bb " is a nice string because both 'B' and 'b' appear. The whole string is a substring.

**Example 3:**

**Input:** s =  "c "
**Output:**  " "
**Explanation:** There are no nice substrings.

**Constraints:**

*   `1 <= s.length <= 100`
*   `s` consists of uppercase and lowercase English letters.
Form Array by Concatenating Subarrays of Another Array

You are given a 2D integer array `groups` of length `n`. You are also given an integer array `nums`.

You are asked if you can choose `n` **disjoint** subarrays from the array `nums` such that the `ith` subarray is equal to `groups[i]` (**0-indexed**), and if `i > 0`, the `(i-1)th` subarray appears **before** the `ith` subarray in `nums` (i.e. the subarrays must be in the same order as `groups`).

Return `true` _if you can do this task, and_ `false` _otherwise_.

Note that the subarrays are **disjoint** if and only if there is no index `k` such that `nums[k]` belongs to more than one subarray. A subarray is a contiguous sequence of elements within an array.

**Example 1:**

**Input:** groups = \[\[1,-1,-1\],\[3,-2,0\]\], nums = \[1,-1,0,1,-1,-1,3,-2,0\]
**Output:** true
**Explanation:** You can choose the 0th subarray as \[1,-1,0,**1,-1,-1**,3,-2,0\] and the 1st one as \[1,-1,0,1,-1,-1,**3,-2,0**\].
These subarrays are disjoint as they share no common nums\[k\] element.

**Example 2:**

**Input:** groups = \[\[10,-2\],\[1,2,3,4\]\], nums = \[1,2,3,4,10,-2\]
**Output:** false
**Explanation:** Note that choosing the subarrays \[**1,2,3,4**,10,-2\] and \[1,2,3,4,**10,-2**\] is incorrect because they are not in the same order as in groups.
\[10,-2\] must come before \[1,2,3,4\].

**Example 3:**

**Input:** groups = \[\[1,2,3\],\[3,4\]\], nums = \[7,7,1,2,3,4,7,7\]
**Output:** false
**Explanation:** Note that choosing the subarrays \[7,7,**1,2,3**,4,7,7\] and \[7,7,1,2,**3,4**,7,7\] is invalid because they are not disjoint.
They share a common elements nums\[4\] (0-indexed).

**Constraints:**

*   `groups.length == n`
*   `1 <= n <= 103`
*   `1 <= groups[i].length, sum(groups[i].length) <= 103`
*   `1 <= nums.length <= 103`
*   `-107 <= groups[i][j], nums[k] <= 107`
Map of Highest Peak

You are given an integer matrix `isWater` of size `m x n` that represents a map of **land** and **water** cells.

*   If `isWater[i][j] == 0`, cell `(i, j)` is a **land** cell.
*   If `isWater[i][j] == 1`, cell `(i, j)` is a **water** cell.

You must assign each cell a height in a way that follows these rules:

*   The height of each cell must be non-negative.
*   If the cell is a **water** cell, its height must be `0`.
*   Any two adjacent cells must have an absolute height difference of **at most** `1`. A cell is adjacent to another cell if the former is directly north, east, south, or west of the latter (i.e., their sides are touching).

Find an assignment of heights such that the maximum height in the matrix is **maximized**.

Return _an integer matrix_ `height` _of size_ `m x n` _where_ `height[i][j]` _is cell_ `(i, j)`_'s height. If there are multiple solutions, return **any** of them_.

**Example 1:**

**Input:** isWater = \[\[0,1\],\[0,0\]\]
**Output:** \[\[1,0\],\[2,1\]\]
**Explanation:** The image shows the assigned heights of each cell.
The blue cell is the water cell, and the green cells are the land cells.

**Example 2:**

**Input:** isWater = \[\[0,0,1\],\[1,0,0\],\[0,0,0\]\]
**Output:** \[\[1,1,0\],\[0,1,1\],\[1,2,2\]\]
**Explanation:** A height of 2 is the maximum possible height of any assignment.
Any height assignment that has a maximum height of 2 while still meeting the rules will also be accepted.

**Constraints:**

*   `m == isWater.length`
*   `n == isWater[i].length`
*   `1 <= m, n <= 1000`
*   `isWater[i][j]` is `0` or `1`.
*   There is at least **one** water cell.
Tree of Coprimes

There is a tree (i.e., a connected, undirected graph that has no cycles) consisting of `n` nodes numbered from `0` to `n - 1` and exactly `n - 1` edges. Each node has a value associated with it, and the **root** of the tree is node `0`.

To represent this tree, you are given an integer array `nums` and a 2D array `edges`. Each `nums[i]` represents the `ith` node's value, and each `edges[j] = [uj, vj]` represents an edge between nodes `uj` and `vj` in the tree.

Two values `x` and `y` are **coprime** if `gcd(x, y) == 1` where `gcd(x, y)` is the **greatest common divisor** of `x` and `y`.

An ancestor of a node `i` is any other node on the shortest path from node `i` to the **root**. A node is **not** considered an ancestor of itself.

Return _an array_ `ans` _of size_ `n`, _where_ `ans[i]` _is the closest ancestor to node_ `i` _such that_ `nums[i]` _and_ `nums[ans[i]]` are **coprime**, or `-1` _if there is no such ancestor_.

**Example 1:**

**Input:** nums = \[2,3,3,2\], edges = \[\[0,1\],\[1,2\],\[1,3\]\]
**Output:** \[-1,0,0,1\]
**Explanation:** In the above figure, each node's value is in parentheses.
- Node 0 has no coprime ancestors.
- Node 1 has only one ancestor, node 0. Their values are coprime (gcd(2,3) == 1).
- Node 2 has two ancestors, nodes 1 and 0. Node 1's value is not coprime (gcd(3,3) == 3), but node 0's
  value is (gcd(2,3) == 1), so node 0 is the closest valid ancestor.
- Node 3 has two ancestors, nodes 1 and 0. It is coprime with node 1 (gcd(3,2) == 1), so node 1 is its
  closest valid ancestor.

**Example 2:**

**Input:** nums = \[5,6,10,2,3,6,15\], edges = \[\[0,1\],\[0,2\],\[1,3\],\[1,4\],\[2,5\],\[2,6\]\]
**Output:** \[-1,0,-1,0,0,0,-1\]

**Constraints:**

*   `nums.length == n`
*   `1 <= nums[i] <= 50`
*   `1 <= n <= 105`
*   `edges.length == n - 1`
*   `edges[j].length == 2`
*   `0 <= uj, vj < n`
*   `uj != vj`
Merge Strings Alternately

You are given two strings `word1` and `word2`. Merge the strings by adding letters in alternating order, starting with `word1`. If a string is longer than the other, append the additional letters onto the end of the merged string.

Return _the merged string._

**Example 1:**

**Input:** word1 =  "abc ", word2 =  "pqr "
**Output:**  "apbqcr "
**Explanation:** The merged string will be merged as so:
word1:  a   b   c
word2:    p   q   r
merged: a p b q c r

**Example 2:**

**Input:** word1 =  "ab ", word2 =  "pqrs "
**Output:**  "apbqrs "
**Explanation:** Notice that as word2 is longer,  "rs " is appended to the end.
word1:  a   b 
word2:    p   q   r   s
merged: a p b q   r   s

**Example 3:**

**Input:** word1 =  "abcd ", word2 =  "pq "
**Output:**  "apbqcd "
**Explanation:** Notice that as word1 is longer,  "cd " is appended to the end.
word1:  a   b   c   d
word2:    p   q 
merged: a p b q c   d

**Constraints:**

*   `1 <= word1.length, word2.length <= 100`
*   `word1` and `word2` consist of lowercase English letters.
Minimum Number of Operations to Move All Balls to Each Box

You have `n` boxes. You are given a binary string `boxes` of length `n`, where `boxes[i]` is `'0'` if the `ith` box is **empty**, and `'1'` if it contains **one** ball.

In one operation, you can move **one** ball from a box to an adjacent box. Box `i` is adjacent to box `j` if `abs(i - j) == 1`. Note that after doing so, there may be more than one ball in some boxes.

Return an array `answer` of size `n`, where `answer[i]` is the **minimum** number of operations needed to move all the balls to the `ith` box.

Each `answer[i]` is calculated considering the **initial** state of the boxes.

**Example 1:**

**Input:** boxes =  "110 "
**Output:** \[1,1,3\]
**Explanation:** The answer for each box is as follows:
1) First box: you will have to move one ball from the second box to the first box in one operation.
2) Second box: you will have to move one ball from the first box to the second box in one operation.
3) Third box: you will have to move one ball from the first box to the third box in two operations, and move one ball from the second box to the third box in one operation.

**Example 2:**

**Input:** boxes =  "001011 "
**Output:** \[11,8,5,4,3,4\]

**Constraints:**

*   `n == boxes.length`
*   `1 <= n <= 2000`
*   `boxes[i]` is either `'0'` or `'1'`.
Maximum Score from Performing Multiplication Operations

You are given two **0-indexed** integer arrays `nums` and `multipliers` of size `n` and `m` respectively, where `n >= m`.

You begin with a score of `0`. You want to perform **exactly** `m` operations. On the `ith` operation (**0-indexed**) you will:

*   Choose one integer `x` from **either the start or the end** of the array `nums`.
*   Add `multipliers[i] * x` to your score.
    *   Note that `multipliers[0]` corresponds to the first operation, `multipliers[1]` to the second operation, and so on.
*   Remove `x` from `nums`.

Return _the **maximum** score after performing_ `m` _operations._

**Example 1:**

**Input:** nums = \[1,2,3\], multipliers = \[3,2,1\]
**Output:** 14
**Explanation:** An optimal solution is as follows:
- Choose from the end, \[1,2,**3**\], adding 3 \* 3 = 9 to the score.
- Choose from the end, \[1,**2**\], adding 2 \* 2 = 4 to the score.
- Choose from the end, \[**1**\], adding 1 \* 1 = 1 to the score.
The total score is 9 + 4 + 1 = 14.

**Example 2:**

**Input:** nums = \[-5,-3,-3,-2,7,1\], multipliers = \[-10,-5,3,4,6\]
**Output:** 102
**Explanation:** An optimal solution is as follows:
- Choose from the start, \[**\-5**,-3,-3,-2,7,1\], adding -5 \* -10 = 50 to the score.
- Choose from the start, \[**\-3**,-3,-2,7,1\], adding -3 \* -5 = 15 to the score.
- Choose from the start, \[**\-3**,-2,7,1\], adding -3 \* 3 = -9 to the score.
- Choose from the end, \[-2,7,**1**\], adding 1 \* 4 = 4 to the score.
- Choose from the end, \[-2,**7**\], adding 7 \* 6 = 42 to the score. 
The total score is 50 + 15 - 9 + 4 + 42 = 102.

**Constraints:**

*   `n == nums.length`
*   `m == multipliers.length`
*   `1 <= m <= 300`
*   `m <= n <= 105`
*   `-1000 <= nums[i], multipliers[i] <= 1000`
Maximize Palindrome Length From Subsequences

You are given two strings, `word1` and `word2`. You want to construct a string in the following manner:

*   Choose some **non-empty** subsequence `subsequence1` from `word1`.
*   Choose some **non-empty** subsequence `subsequence2` from `word2`.
*   Concatenate the subsequences: `subsequence1 + subsequence2`, to make the string.

Return _the **length** of the longest **palindrome** that can be constructed in the described manner._ If no palindromes can be constructed, return `0`.

A **subsequence** of a string `s` is a string that can be made by deleting some (possibly none) characters from `s` without changing the order of the remaining characters.

A **palindrome** is a string that reads the same forward as well as backward.

**Example 1:**

**Input:** word1 =  "cacb ", word2 =  "cbba "
**Output:** 5
**Explanation:** Choose  "ab " from word1 and  "cba " from word2 to make  "abcba ", which is a palindrome.

**Example 2:**

**Input:** word1 =  "ab ", word2 =  "ab "
**Output:** 3
**Explanation:** Choose  "ab " from word1 and  "a " from word2 to make  "aba ", which is a palindrome.

**Example 3:**

**Input:** word1 =  "aa ", word2 =  "bb "
**Output:** 0
**Explanation:** You cannot construct a palindrome from the described method, so return 0.

**Constraints:**

*   `1 <= word1.length, word2.length <= 1000`
*   `word1` and `word2` consist of lowercase English letters.
Sort Features by Popularity

You are given a string array `features` where `features[i]` is a single word that represents the name of a feature of the latest product you are working on. You have made a survey where users have reported which features they like. You are given a string array `responses`, where each `responses[i]` is a string containing space-separated words.

The **popularity** of a feature is the number of `responses[i]` that contain the feature. You want to sort the features in non-increasing order by their popularity. If two features have the same popularity, order them by their original index in `features`. Notice that one response could contain the same feature multiple times; this feature is only counted once in its popularity.

Return _the features in sorted order._

**Example 1:**

**Input:** features = \[ "cooler ", "lock ", "touch "\], responses = \[ "i like cooler cooler ", "lock touch cool ", "locker like touch "\]
**Output:** \[ "touch ", "cooler ", "lock "\]
**Explanation:** appearances( "cooler ") = 1, appearances( "lock ") = 1, appearances( "touch ") = 2. Since  "cooler " and  "lock " both had 1 appearance,  "cooler " comes first because  "cooler " came first in the features array.

**Example 2:**

**Input:** features = \[ "a ", "aa ", "b ", "c "\], responses = \[ "a ", "a aa ", "a a a a a ", "b a "\]
**Output:** \[ "a ", "aa ", "b ", "c "\]

**Constraints:**

*   `1 <= features.length <= 104`
*   `1 <= features[i].length <= 10`
*   `features` contains no duplicates.
*   `features[i]` consists of lowercase letters.
*   `1 <= responses.length <= 102`
*   `1 <= responses[i].length <= 103`
*   `responses[i]` consists of lowercase letters and spaces.
*   `responses[i]` contains no two consecutive spaces.
*   `responses[i]` has no leading or trailing spaces.
Count Items Matching a Rule

You are given an array `items`, where each `items[i] = [typei, colori, namei]` describes the type, color, and name of the `ith` item. You are also given a rule represented by two strings, `ruleKey` and `ruleValue`.

The `ith` item is said to match the rule if **one** of the following is true:

*   `ruleKey == "type "` and `ruleValue == typei`.
*   `ruleKey == "color "` and `ruleValue == colori`.
*   `ruleKey == "name "` and `ruleValue == namei`.

Return _the number of items that match the given rule_.

**Example 1:**

**Input:** items = \[\[ "phone ", "blue ", "pixel "\],\[ "computer ", "silver ", "lenovo "\],\[ "phone ", "gold ", "iphone "\]\], ruleKey =  "color ", ruleValue =  "silver "
**Output:** 1
**Explanation:** There is only one item matching the given rule, which is \[ "computer ", "silver ", "lenovo "\].

**Example 2:**

**Input:** items = \[\[ "phone ", "blue ", "pixel "\],\[ "computer ", "silver ", "phone "\],\[ "phone ", "gold ", "iphone "\]\], ruleKey =  "type ", ruleValue =  "phone "
**Output:** 2
**Explanation:** There are only two items matching the given rule, which are \[ "phone ", "blue ", "pixel "\] and \[ "phone ", "gold ", "iphone "\]. Note that the item \[ "computer ", "silver ", "phone "\] does not match.

**Constraints:**

*   `1 <= items.length <= 104`
*   `1 <= typei.length, colori.length, namei.length, ruleValue.length <= 10`
*   `ruleKey` is equal to either `"type "`, `"color "`, or `"name "`.
*   All strings consist only of lowercase letters.