bowang0911/leetcode huggingface dataset:
Sentence Screen Fitting

Given a `rows x cols` screen and a `sentence` represented as a list of strings, return _the number of times the given sentence can be fitted on the screen_.

The order of words in the sentence must remain unchanged, and a word cannot be split into two lines. A single space must separate two consecutive words in a line.

**Example 1:**

**Input:** sentence = \[ "hello ", "world "\], rows = 2, cols = 8
**Output:** 1
**Explanation:**
hello---
world---
The character '-' signifies an empty space on the screen.

**Example 2:**

**Input:** sentence = \[ "a ",  "bcd ",  "e "\], rows = 3, cols = 6
**Output:** 2
**Explanation:**
a-bcd- 
e-a---
bcd-e-
The character '-' signifies an empty space on the screen.

**Example 3:**

**Input:** sentence = \[ "i ", "had ", "apple ", "pie "\], rows = 4, cols = 5
**Output:** 1
**Explanation:**
i-had
apple
pie-i
had--
The character '-' signifies an empty space on the screen.

**Constraints:**

*   `1 <= sentence.length <= 100`
*   `1 <= sentence[i].length <= 10`
*   `sentence[i]` consists of lowercase English letters.
*   `1 <= rows, cols <= 2 * 104`
Battleships in a Board

Given an `m x n` matrix `board` where each cell is a battleship `'X'` or empty `'.'`, return _the number of the **battleships** on_ `board`.

**Battleships** can only be placed horizontally or vertically on `board`. In other words, they can only be made of the shape `1 x k` (`1` row, `k` columns) or `k x 1` (`k` rows, `1` column), where `k` can be of any size. At least one horizontal or vertical cell separates between two battleships (i.e., there are no adjacent battleships).

**Example 1:**

**Input:** board = \[\[ "X ", ". ", ". ", "X "\],\[ ". ", ". ", ". ", "X "\],\[ ". ", ". ", ". ", "X "\]\]
**Output:** 2

**Example 2:**

**Input:** board = \[\[ ". "\]\]
**Output:** 0

**Constraints:**

*   `m == board.length`
*   `n == board[i].length`
*   `1 <= m, n <= 200`
*   `board[i][j]` is either `'.'` or `'X'`.

**Follow up:** Could you do it in one-pass, using only `O(1)` extra memory and without modifying the values `board`?
Strong Password Checker

A password is considered strong if the below conditions are all met:

*   It has at least `6` characters and at most `20` characters.
*   It contains at least **one lowercase** letter, at least **one uppercase** letter, and at least **one digit**.
*   It does not contain three repeating characters in a row (i.e., `"B**aaa**bb0 "` is weak, but `"B**aa**b**a**0 "` is strong).

Given a string `password`, return _the minimum number of steps required to make `password` strong. if `password` is already strong, return `0`._

In one step, you can:

*   Insert one character to `password`,
*   Delete one character from `password`, or
*   Replace one character of `password` with another character.

**Example 1:**

**Input:** password = "a"
**Output:** 5

**Example 2:**

**Input:** password = "aA1"
**Output:** 3

**Example 3:**

**Input:** password = "1337C0d3"
**Output:** 0

**Constraints:**

*   `1 <= password.length <= 50`
*   `password` consists of letters, digits, dot `'.'` or exclamation mark `'!'`.
Maximum XOR of Two Numbers in an Array

Given an integer array `nums`, return _the maximum result of_ `nums[i] XOR nums[j]`, where `0 <= i <= j < n`.

**Example 1:**

**Input:** nums = \[3,10,5,25,2,8\]
**Output:** 28
**Explanation:** The maximum result is 5 XOR 25 = 28.

**Example 2:**

**Input:** nums = \[14,70,53,83,49,91,36,80,92,51,66,70\]
**Output:** 127

**Constraints:**

*   `1 <= nums.length <= 2 * 105`
*   `0 <= nums[i] <= 231 - 1`
Valid Word Square

Given an array of strings `words`, return `true` _if it forms a valid **word square**_.

A sequence of strings forms a valid **word square** if the `kth` row and column read the same string, where `0 <= k < max(numRows, numColumns)`.

**Example 1:**

**Input:** words = \[ "abcd ", "bnrt ", "crmy ", "dtye "\]
**Output:** true
**Explanation:**
The 1st row and 1st column both read  "abcd ".
The 2nd row and 2nd column both read  "bnrt ".
The 3rd row and 3rd column both read  "crmy ".
The 4th row and 4th column both read  "dtye ".
Therefore, it is a valid word square.

**Example 2:**

**Input:** words = \[ "abcd ", "bnrt ", "crm ", "dt "\]
**Output:** true
**Explanation:**
The 1st row and 1st column both read  "abcd ".
The 2nd row and 2nd column both read  "bnrt ".
The 3rd row and 3rd column both read  "crm ".
The 4th row and 4th column both read  "dt ".
Therefore, it is a valid word square.

**Example 3:**

**Input:** words = \[ "ball ", "area ", "read ", "lady "\]
**Output:** false
**Explanation:**
The 3rd row reads  "read " while the 3rd column reads  "lead ".
Therefore, it is NOT a valid word square.

**Constraints:**

*   `1 <= words.length <= 500`
*   `1 <= words[i].length <= 500`
*   `words[i]` consists of only lowercase English letters.
Reconstruct Original Digits from English

Given a string `s` containing an out-of-order English representation of digits `0-9`, return _the digits in **ascending** order_.

**Example 1:**

**Input:** s = "owoztneoer"
**Output:** "012"

**Example 2:**

**Input:** s = "fviefuro"
**Output:** "45"

**Constraints:**

*   `1 <= s.length <= 105`
*   `s[i]` is one of the characters `[ "e ", "g ", "f ", "i ", "h ", "o ", "n ", "s ", "r ", "u ", "t ", "w ", "v ", "x ", "z "]`.
*   `s` is **guaranteed** to be valid.
Longest Repeating Character Replacement

You are given a string `s` and an integer `k`. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most `k` times.

Return _the length of the longest substring containing the same letter you can get after performing the above operations_.

**Example 1:**

**Input:** s =  "ABAB ", k = 2
**Output:** 4
**Explanation:** Replace the two 'A's with two 'B's or vice versa.

**Example 2:**

**Input:** s =  "AABABBA ", k = 1
**Output:** 4
**Explanation:** Replace the one 'A' in the middle with 'B' and form  "AABBBBA ".
The substring  "BBBB " has the longest repeating letters, which is 4.

**Constraints:**

*   `1 <= s.length <= 105`
*   `s` consists of only uppercase English letters.
*   `0 <= k <= s.length`
Word Squares

Given an array of **unique** strings `words`, return _all the_ **[word squares](https://en.wikipedia.org/wiki/Word_square)** _you can build from_ `words`. The same word from `words` can be used **multiple times**. You can return the answer in **any order**.

A sequence of strings forms a valid **word square** if the `kth` row and column read the same string, where `0 <= k < max(numRows, numColumns)`.

*   For example, the word sequence `[ "ball ", "area ", "lead ", "lady "]` forms a word square because each word reads the same both horizontally and vertically.

**Example 1:**

**Input:** words = \[ "area ", "lead ", "wall ", "lady ", "ball "\]
**Output:** \[\[ "ball ", "area ", "lead ", "lady "\],\[ "wall ", "area ", "lead ", "lady "\]\]
**Explanation:**
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

**Example 2:**

**Input:** words = \[ "abat ", "baba ", "atan ", "atal "\]
**Output:** \[\[ "baba ", "abat ", "baba ", "atal "\],\[ "baba ", "abat ", "baba ", "atan "\]\]
**Explanation:**
The output consists of two word squares. The order of output does not matter (just the order of words in each word square matters).

**Constraints:**

*   `1 <= words.length <= 1000`
*   `1 <= words[i].length <= 4`
*   All `words[i]` have the same length.
*   `words[i]` consists of only lowercase English letters.
*   All `words[i]` are **unique**.
Convert Binary Search Tree to Sorted Doubly Linked List

Convert a **Binary Search Tree** to a sorted **Circular Doubly-Linked List** in place.

You can think of the left and right pointers as synonymous to the predecessor and successor pointers in a doubly-linked list. For a circular doubly linked list, the predecessor of the first element is the last element, and the successor of the last element is the first element.

We want to do the transformation **in place**. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. You should return the pointer to the smallest element of the linked list.

**Example 1:**

**Input:** root = \[4,2,5,1,3\]

 
**Output:** \[1,2,3,4,5\]

**Explanation:** The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.
 

**Example 2:**

**Input:** root = \[2,1,3\]
**Output:** \[1,2,3\]

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 2000]`.
*   `-1000 <= Node.val <= 1000`
*   All the values of the tree are **unique**.
Construct Quad Tree

Given a `n * n` matrix `grid` of `0's` and `1's` only. We want to represent `grid` with a Quad-Tree.

Return _the root of the Quad-Tree representing_ `grid`.

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

*   `val`: True if the node represents a grid of 1's or False if the node represents a grid of 0's. Notice that you can assign the `val` to True or False when `isLeaf` is False, and both are accepted in the answer.
*   `isLeaf`: True if the node is a leaf node on the tree or False if the node has four children.

class Node {
    public boolean val;
    public boolean isLeaf;
    public Node topLeft;
    public Node topRight;
    public Node bottomLeft;
    public Node bottomRight;
}

We can construct a Quad-Tree from a two-dimensional area using the following steps:

1.  If the current grid has the same value (i.e all `1's` or all `0's`) set `isLeaf` True and set `val` to the value of the grid and set the four children to Null and stop.
2.  If the current grid has different values, set `isLeaf` to False and set `val` to any value and divide the current grid into four sub-grids as shown in the photo.
3.  Recurse for each of the children with the proper sub-grid.

If you want to know more about the Quad-Tree, you can refer to the [wiki](https://en.wikipedia.org/wiki/Quadtree).

**Quad-Tree format:**

You don't need to read this section for solving the problem. This is only if you want to understand the output format here. The output represents the serialized format of a Quad-Tree using level order traversal, where `null` signifies a path terminator where no node exists below.

It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list `[isLeaf, val]`.

If the value of `isLeaf` or `val` is True we represent it as **1** in the list `[isLeaf, val]` and if the value of `isLeaf` or `val` is False we represent it as **0**.

**Example 1:**

**Input:** grid = \[\[0,1\],\[1,0\]\]
**Output:** \[\[0,1\],\[1,0\],\[1,1\],\[1,1\],\[1,0\]\]
**Explanation:** The explanation of this example is shown below:
Notice that 0 represnts False and 1 represents True in the photo representing the Quad-Tree.
 

**Example 2:**

**Input:** grid = \[\[1,1,1,1,0,0,0,0\],\[1,1,1,1,0,0,0,0\],\[1,1,1,1,1,1,1,1\],\[1,1,1,1,1,1,1,1\],\[1,1,1,1,0,0,0,0\],\[1,1,1,1,0,0,0,0\],\[1,1,1,1,0,0,0,0\],\[1,1,1,1,0,0,0,0\]\]
**Output:** \[\[0,1\],\[1,1\],\[0,1\],\[1,1\],\[1,0\],null,null,null,null,\[1,0\],\[1,0\],\[1,1\],\[1,1\]\]
**Explanation:** All values in the grid are not the same. We divide the grid into four sub-grids.
The topLeft, bottomLeft and bottomRight each has the same value.
The topRight have different values so we divide it into 4 sub-grids where each has the same value.
Explanation is shown in the photo below:
 

**Constraints:**

*   `n == grid.length == grid[i].length`
*   `n == 2x` where `0 <= x <= 6`
Serialize and Deserialize N-ary Tree

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize an N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that an N-ary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following `3-ary` tree

as `[1 [3[5 6] 2 4]]`. Note that this is just an example, you do not necessarily need to follow this format.

Or you can follow LeetCode's level order traversal serialization format, where each group of children is separated by the null value.

For example, the above tree may be serialized as `[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]`.

You do not necessarily need to follow the above-suggested formats, there are many more different formats that work so please be creative and come up with different approaches yourself.

**Example 1:**

**Input:** root = \[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14\]
**Output:** \[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14\]

**Example 2:**

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

**Example 3:**

**Input:** root = \[\]
**Output:** \[\]

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 104]`.
*   `0 <= Node.val <= 104`
*   The height of the n-ary tree is less than or equal to `1000`
*   Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
N-ary Tree Level Order Traversal

Given an n-ary tree, return the _level order_ traversal of its nodes' values.

_Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples)._

**Example 1:**

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

**Example 2:**

**Input:** root = \[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14\]
**Output:** \[\[1\],\[2,3,4,5\],\[6,7,8,9,10\],\[11,12,13\],\[14\]\]

**Constraints:**

*   The height of the n-ary tree is less than or equal to `1000`
*   The total number of nodes is between `[0, 104]`
Flatten a Multilevel Doubly Linked List

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional **child pointer**. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a **multilevel data structure** as shown in the example below.

Given the `head` of the first level of the list, **flatten** the list so that all the nodes appear in a single-level, doubly linked list. Let `curr` be a node with a child list. The nodes in the child list should appear **after** `curr` and **before** `curr.next` in the flattened list.

Return _the_ `head` _of the flattened list. The nodes in the list must have **all** of their child pointers set to_ `null`.

**Example 1:**

**Input:** head = \[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12\]
**Output:** \[1,2,3,7,8,11,12,9,10,4,5,6\]
**Explanation:** The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:
 

**Example 2:**

**Input:** head = \[1,2,null,3\]
**Output:** \[1,3,2\]
**Explanation:** The multilevel linked list in the input is shown.
After flattening the multilevel linked list it becomes:
 

**Example 3:**

**Input:** head = \[\]
**Output:** \[\]
**Explanation:** There could be empty list in the input.

**Constraints:**

*   The number of Nodes will not exceed `1000`.
*   `1 <= Node.val <= 105`

**How the multilevel linked list is represented in test cases:**

We use the multilevel linked list from **Example 1** above:

 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

The serialization of each level is as follows:

\[1,2,3,4,5,6,null\]
\[7,8,9,10,null\]
\[11,12,null\]

To serialize all levels together, we will add nulls in each level to signify no node connects to the upper node of the previous level. The serialization becomes:

\[1,    2,    3, 4, 5, 6, null\]
             |
\[null, null, 7,    8, 9, 10, null\]
                   |
\[            null, 11, 12, null\]

Merging the serialization of each level and removing trailing nulls we obtain:

\[1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12\]
Encode N-ary Tree to Binary Tree

Design an algorithm to encode an N-ary tree into a binary tree and decode the binary tree to get the original N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. Similarly, a binary tree is a rooted tree in which each node has no more than 2 children. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that an N-ary tree can be encoded to a binary tree and this binary tree can be decoded to the original N-nary tree structure.

_Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See following example)._

For example, you may encode the following `3-ary` tree to a binary tree in this way:

**Input:** root = \[1,null,3,2,4,null,5,6\]

Note that the above is just an example which _might or might not_ work. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

**Example 1:**

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

**Example 2:**

**Input:** root = \[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14\]
**Output:** \[1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14\]

**Example 3:**

**Input:** root = \[\]
**Output:** \[\]

**Constraints:**

*   The number of nodes in the tree is in the range `[0, 104]`.
*   `0 <= Node.val <= 104`
*   The height of the n-ary tree is less than or equal to `1000`
*   Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
All O`one Data Structure

Design a data structure to store the strings' count with the ability to return the strings with minimum and maximum counts.

Implement the `AllOne` class:

*   `AllOne()` Initializes the object of the data structure.
*   `inc(String key)` Increments the count of the string `key` by `1`. If `key` does not exist in the data structure, insert it with count `1`.
*   `dec(String key)` Decrements the count of the string `key` by `1`. If the count of `key` is `0` after the decrement, remove it from the data structure. It is guaranteed that `key` exists in the data structure before the decrement.
*   `getMaxKey()` Returns one of the keys with the maximal count. If no element exists, return an empty string `" "`.
*   `getMinKey()` Returns one of the keys with the minimum count. If no element exists, return an empty string `" "`.

**Note** that each function must run in `O(1)` average time complexity.

**Example 1:**

**Input**
\[ "AllOne ",  "inc ",  "inc ",  "getMaxKey ",  "getMinKey ",  "inc ",  "getMaxKey ",  "getMinKey "\]
\[\[\], \[ "hello "\], \[ "hello "\], \[\], \[\], \[ "leet "\], \[\], \[\]\]
**Output**
\[null, null, null,  "hello ",  "hello ", null,  "hello ",  "leet "\]

**Explanation**
AllOne allOne = new AllOne();
allOne.inc( "hello ");
allOne.inc( "hello ");
allOne.getMaxKey(); // return  "hello "
allOne.getMinKey(); // return  "hello "
allOne.inc( "leet ");
allOne.getMaxKey(); // return  "hello "
allOne.getMinKey(); // return  "leet "

**Constraints:**

*   `1 <= key.length <= 10`
*   `key` consists of lowercase English letters.
*   It is guaranteed that for each call to `dec`, `key` is existing in the data structure.
*   At most `5 * 104` calls will be made to `inc`, `dec`, `getMaxKey`, and `getMinKey`.
Minimum Genetic Mutation

A gene string can be represented by an 8-character long string, with choices from `'A'`, `'C'`, `'G'`, and `'T'`.

Suppose we need to investigate a mutation from a gene string `startGene` to a gene string `endGene` where one mutation is defined as one single character changed in the gene string.

*   For example, `"AACCGGTT " --> "AACCGGTA "` is one mutation.

There is also a gene bank `bank` that records all the valid gene mutations. A gene must be in `bank` to make it a valid gene string.

Given the two gene strings `startGene` and `endGene` and the gene bank `bank`, return _the minimum number of mutations needed to mutate from_ `startGene` _to_ `endGene`. If there is no such a mutation, return `-1`.

Note that the starting point is assumed to be valid, so it might not be included in the bank.

**Example 1:**

**Input:** startGene =  "AACCGGTT ", endGene =  "AACCGGTA ", bank = \[ "AACCGGTA "\]
**Output:** 1

**Example 2:**

**Input:** startGene =  "AACCGGTT ", endGene =  "AAACGGTA ", bank = \[ "AACCGGTA ", "AACCGCTA ", "AAACGGTA "\]
**Output:** 2

**Constraints:**

*   `0 <= bank.length <= 10`
*   `startGene.length == endGene.length == bank[i].length == 8`
*   `startGene`, `endGene`, and `bank[i]` consist of only the characters `['A', 'C', 'G', 'T']`.
Number of Segments in a String

Given a string `s`, return _the number of segments in the string_.

A **segment** is defined to be a contiguous sequence of **non-space characters**.

**Example 1:**

**Input:** s =  "Hello, my name is John "
**Output:** 5
**Explanation:** The five segments are \[ "Hello, ",  "my ",  "name ",  "is ",  "John "\]

**Example 2:**

**Input:** s =  "Hello "
**Output:** 1

**Constraints:**

*   `0 <= s.length <= 300`
*   `s` consists of lowercase and uppercase English letters, digits, or one of the following characters `"!@#$%^&*()_+-=',.: "`.
*   The only space character in `s` is `' '`.
Non-overlapping Intervals

Given an array of intervals `intervals` where `intervals[i] = [starti, endi]`, return _the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping_.

**Example 1:**

**Input:** intervals = \[\[1,2\],\[2,3\],\[3,4\],\[1,3\]\]
**Output:** 1
**Explanation:** \[1,3\] can be removed and the rest of the intervals are non-overlapping.

**Example 2:**

**Input:** intervals = \[\[1,2\],\[1,2\],\[1,2\]\]
**Output:** 2
**Explanation:** You need to remove two \[1,2\] to make the rest of the intervals non-overlapping.

**Example 3:**

**Input:** intervals = \[\[1,2\],\[2,3\]\]
**Output:** 0
**Explanation:** You don't need to remove any of the intervals since they're already non-overlapping.

**Constraints:**

*   `1 <= intervals.length <= 105`
*   `intervals[i].length == 2`
*   `-5 * 104 <= starti < endi <= 5 * 104`
Find Right Interval

You are given an array of `intervals`, where `intervals[i] = [starti, endi]` and each `starti` is **unique**.

The **right interval** for an interval `i` is an interval `j` such that `startj >= endi` and `startj` is **minimized**. Note that `i` may equal `j`.

Return _an array of **right interval** indices for each interval `i`_. If no **right interval** exists for interval `i`, then put `-1` at index `i`.

**Example 1:**

**Input:** intervals = \[\[1,2\]\]
**Output:** \[-1\]
**Explanation:** There is only one interval in the collection, so it outputs -1.

**Example 2:**

**Input:** intervals = \[\[3,4\],\[2,3\],\[1,2\]\]
**Output:** \[-1,0,1\]
**Explanation:** There is no right interval for \[3,4\].
The right interval for \[2,3\] is \[3,4\] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for \[1,2\] is \[2,3\] since start1 = 2 is the smallest start that is >= end2 = 2.

**Example 3:**

**Input:** intervals = \[\[1,4\],\[2,3\],\[3,4\]\]
**Output:** \[-1,2,-1\]
**Explanation:** There is no right interval for \[1,4\] and \[3,4\].
The right interval for \[2,3\] is \[3,4\] since start2 = 3 is the smallest start that is >= end1 = 3.

**Constraints:**

*   `1 <= intervals.length <= 2 * 104`
*   `intervals[i].length == 2`
*   `-106 <= starti <= endi <= 106`
*   The start point of each interval is **unique**.