bowang0911/leetcode huggingface dataset:
Minimum Rounds to Complete All Tasks

You are given a **0-indexed** integer array `tasks`, where `tasks[i]` represents the difficulty level of a task. In each round, you can complete either 2 or 3 tasks of the **same difficulty level**.

Return _the **minimum** rounds required to complete all the tasks, or_ `-1` _if it is not possible to complete all the tasks._

**Example 1:**

**Input:** tasks = \[2,2,3,3,2,4,4,4,4,4\]
**Output:** 4
**Explanation:** To complete all the tasks, a possible plan is:
- In the first round, you complete 3 tasks of difficulty level 2. 
- In the second round, you complete 2 tasks of difficulty level 3. 
- In the third round, you complete 3 tasks of difficulty level 4. 
- In the fourth round, you complete 2 tasks of difficulty level 4.  
It can be shown that all the tasks cannot be completed in fewer than 4 rounds, so the answer is 4.

**Example 2:**

**Input:** tasks = \[2,3,3\]
**Output:** -1
**Explanation:** There is only 1 task of difficulty level 2, but in each round, you can only complete either 2 or 3 tasks of the same difficulty level. Hence, you cannot complete all the tasks, and the answer is -1.

**Constraints:**

*   `1 <= tasks.length <= 105`
*   `1 <= tasks[i] <= 109`
Maximum Trailing Zeros in a Cornered Path

You are given a 2D integer array `grid` of size `m x n`, where each cell contains a positive integer.

A **cornered path** is defined as a set of adjacent cells with **at most** one turn. More specifically, the path should exclusively move either **horizontally** or **vertically** up to the turn (if there is one), without returning to a previously visited cell. After the turn, the path will then move exclusively in the **alternate** direction: move vertically if it moved horizontally, and vice versa, also without returning to a previously visited cell.

The **product** of a path is defined as the product of all the values in the path.

Return _the **maximum** number of **trailing zeros** in the product of a cornered path found in_ `grid`.

Note:

*   **Horizontal** movement means moving in either the left or right direction.
*   **Vertical** movement means moving in either the up or down direction.

**Example 1:**

**Input:** grid = \[\[23,17,15,3,20\],\[8,1,20,27,11\],\[9,4,6,2,21\],\[40,9,1,10,6\],\[22,7,4,5,3\]\]
**Output:** 3
**Explanation:** The grid on the left shows a valid cornered path.
It has a product of 15 \* 20 \* 6 \* 1 \* 10 = 18000 which has 3 trailing zeros.
It can be shown that this is the maximum trailing zeros in the product of a cornered path.

The grid in the middle is not a cornered path as it has more than one turn.
The grid on the right is not a cornered path as it requires a return to a previously visited cell.

**Example 2:**

**Input:** grid = \[\[4,3,2\],\[7,6,1\],\[8,8,8\]\]
**Output:** 0
**Explanation:** The grid is shown in the figure above.
There are no cornered paths in the grid that result in a product with a trailing zero.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `1 <= m, n <= 105`
*   `1 <= m * n <= 105`
*   `1 <= grid[i][j] <= 1000`
Longest Path With Different Adjacent Characters

You are given a **tree** (i.e. a connected, undirected graph that has no cycles) **rooted** at node `0` consisting of `n` nodes numbered from `0` to `n - 1`. The tree is represented by a **0-indexed** array `parent` of size `n`, where `parent[i]` is the parent of node `i`. Since node `0` is the root, `parent[0] == -1`.

You are also given a string `s` of length `n`, where `s[i]` is the character assigned to node `i`.

Return _the length of the **longest path** in the tree such that no pair of **adjacent** nodes on the path have the same character assigned to them._

**Example 1:**

**Input:** parent = \[-1,0,0,1,1,2\], s =  "abacbe "
**Output:** 3
**Explanation:** The longest path where each two adjacent nodes have different characters in the tree is the path: 0 -> 1 -> 3. The length of this path is 3, so 3 is returned.
It can be proven that there is no longer path that satisfies the conditions. 

**Example 2:**

**Input:** parent = \[-1,0,0,0\], s =  "aabc "
**Output:** 3
**Explanation:** The longest path where each two adjacent nodes have different characters is the path: 2 -> 0 -> 3. The length of this path is 3, so 3 is returned.

**Constraints:**

*   `n == parent.length == s.length`
*   `1 <= n <= 105`
*   `0 <= parent[i] <= n - 1` for all `i >= 1`
*   `parent[0] == -1`
*   `parent` represents a valid tree.
*   `s` consists of only lowercase English letters.
Maximum Cost of Trip With K Highways

A series of highways connect `n` cities numbered from `0` to `n - 1`. You are given a 2D integer array `highways` where `highways[i] = [city1i, city2i, tolli]` indicates that there is a highway that connects `city1i` and `city2i`, allowing a car to go from `city1i` to `city2i` and **vice versa** for a cost of `tolli`.

You are also given an integer `k`. You are going on a trip that crosses **exactly** `k` highways. You may start at any city, but you may only visit each city **at most** once during your trip.

Return _the **maximum** cost of your trip. If there is no trip that meets the requirements, return_ `-1`_._

**Example 1:**

**Input:** n = 5, highways = \[\[0,1,4\],\[2,1,3\],\[1,4,11\],\[3,2,3\],\[3,4,2\]\], k = 3
**Output:** 17
**Explanation:**
One possible trip is to go from 0 -> 1 -> 4 -> 3. The cost of this trip is 4 + 11 + 2 = 17.
Another possible trip is to go from 4 -> 1 -> 2 -> 3. The cost of this trip is 11 + 3 + 3 = 17.
It can be proven that 17 is the maximum possible cost of any valid trip.

Note that the trip 4 -> 1 -> 0 -> 1 is not allowed because you visit the city 1 twice.

**Example 2:**

**Input:** n = 4, highways = \[\[0,1,3\],\[2,3,2\]\], k = 2
**Output:** -1
**Explanation:** There are no valid trips of length 2, so return -1.

**Constraints:**

*   `2 <= n <= 15`
*   `1 <= highways.length <= 50`
*   `highways[i].length == 3`
*   `0 <= city1i, city2i <= n - 1`
*   `city1i != city2i`
*   `0 <= tolli <= 100`
*   `1 <= k <= 50`
*   There are no duplicate highways.
Intersection of Multiple Arrays

Given a 2D integer array `nums` where `nums[i]` is a non-empty array of **distinct** positive integers, return _the list of integers that are present in **each array** of_ `nums` _sorted in **ascending order**_.

**Example 1:**

**Input:** nums = \[\[**3**,1,2,**4**,5\],\[1,2,**3**,**4**\],\[**3**,**4**,5,6\]\]
**Output:** \[3,4\]
**Explanation:** 
The only integers present in each of nums\[0\] = \[**3**,1,2,**4**,5\], nums\[1\] = \[1,2,**3**,**4**\], and nums\[2\] = \[**3**,**4**,5,6\] are 3 and 4, so we return \[3,4\].

**Example 2:**

**Input:** nums = \[\[1,2,3\],\[4,5,6\]\]
**Output:** \[\]
**Explanation:** 
There does not exist any integer present both in nums\[0\] and nums\[1\], so we return an empty list \[\].

**Constraints:**

*   `1 <= nums.length <= 1000`
*   `1 <= sum(nums[i].length) <= 1000`
*   `1 <= nums[i][j] <= 1000`
*   All the values of `nums[i]` are **unique**.
Count Lattice Points Inside a Circle

Given a 2D integer array `circles` where `circles[i] = [xi, yi, ri]` represents the center `(xi, yi)` and radius `ri` of the `ith` circle drawn on a grid, return _the **number of lattice points**_ _that are present inside **at least one** circle_.

**Note:**

*   A **lattice point** is a point with integer coordinates.
*   Points that lie **on the circumference of a circle** are also considered to be inside it.

**Example 1:**

**Input:** circles = \[\[2,2,1\]\]
**Output:** 5
**Explanation:**
The figure above shows the given circle.
The lattice points present inside the circle are (1, 2), (2, 1), (2, 2), (2, 3), and (3, 2) and are shown in green.
Other points such as (1, 1) and (1, 3), which are shown in red, are not considered inside the circle.
Hence, the number of lattice points present inside at least one circle is 5.

**Example 2:**

**Input:** circles = \[\[2,2,2\],\[3,4,1\]\]
**Output:** 16
**Explanation:**
The figure above shows the given circles.
There are exactly 16 lattice points which are present inside at least one circle. 
Some of them are (0, 2), (2, 0), (2, 4), (3, 2), and (4, 4).

**Constraints:**

*   `1 <= circles.length <= 200`
*   `circles[i].length == 3`
*   `1 <= xi, yi <= 100`
*   `1 <= ri <= min(xi, yi)`
Count Number of Rectangles Containing Each Point

You are given a 2D integer array `rectangles` where `rectangles[i] = [li, hi]` indicates that `ith` rectangle has a length of `li` and a height of `hi`. You are also given a 2D integer array `points` where `points[j] = [xj, yj]` is a point with coordinates `(xj, yj)`.

The `ith` rectangle has its **bottom-left corner** point at the coordinates `(0, 0)` and its **top-right corner** point at `(li, hi)`.

Return _an integer array_ `count` _of length_ `points.length` _where_ `count[j]` _is the number of rectangles that **contain** the_ `jth` _point._

The `ith` rectangle **contains** the `jth` point if `0 <= xj <= li` and `0 <= yj <= hi`. Note that points that lie on the **edges** of a rectangle are also considered to be contained by that rectangle.

**Example 1:**

**Input:** rectangles = \[\[1,2\],\[2,3\],\[2,5\]\], points = \[\[2,1\],\[1,4\]\]
**Output:** \[2,1\]
**Explanation:** 
The first rectangle contains no points.
The second rectangle contains only the point (2, 1).
The third rectangle contains the points (2, 1) and (1, 4).
The number of rectangles that contain the point (2, 1) is 2.
The number of rectangles that contain the point (1, 4) is 1.
Therefore, we return \[2, 1\].

**Example 2:**

**Input:** rectangles = \[\[1,1\],\[2,2\],\[3,3\]\], points = \[\[1,3\],\[1,1\]\]
**Output:** \[1,3\]
**Explanation:**
The first rectangle contains only the point (1, 1).
The second rectangle contains only the point (1, 1).
The third rectangle contains the points (1, 3) and (1, 1).
The number of rectangles that contain the point (1, 3) is 1.
The number of rectangles that contain the point (1, 1) is 3.
Therefore, we return \[1, 3\].

**Constraints:**

*   `1 <= rectangles.length, points.length <= 5 * 104`
*   `rectangles[i].length == points[j].length == 2`
*   `1 <= li, xj <= 109`
*   `1 <= hi, yj <= 100`
*   All the `rectangles` are **unique**.
*   All the `points` are **unique**.
Number of Flowers in Full Bloom

You are given a **0-indexed** 2D integer array `flowers`, where `flowers[i] = [starti, endi]` means the `ith` flower will be in **full bloom** from `starti` to `endi` (**inclusive**). You are also given a **0-indexed** integer array `people` of size `n`, where `poeple[i]` is the time that the `ith` person will arrive to see the flowers.

Return _an integer array_ `answer` _of size_ `n`_, where_ `answer[i]` _is the **number** of flowers that are in full bloom when the_ `ith` _person arrives._

**Example 1:**

**Input:** flowers = \[\[1,6\],\[3,7\],\[9,12\],\[4,13\]\], poeple = \[2,3,7,11\]
**Output:** \[1,2,2,2\]
**Explanation:** The figure above shows the times when the flowers are in full bloom and when the people arrive.
For each person, we return the number of flowers in full bloom during their arrival.

**Example 2:**

**Input:** flowers = \[\[1,10\],\[3,3\]\], poeple = \[3,3,2\]
**Output:** \[2,2,1\]
**Explanation:** The figure above shows the times when the flowers are in full bloom and when the people arrive.
For each person, we return the number of flowers in full bloom during their arrival.

**Constraints:**

*   `1 <= flowers.length <= 5 * 104`
*   `flowers[i].length == 2`
*   `1 <= starti <= endi <= 109`
*   `1 <= people.length <= 5 * 104`
*   `1 <= people[i] <= 109`
Count Prefixes of a Given String

You are given a string array `words` and a string `s`, where `words[i]` and `s` comprise only of **lowercase English letters**.

Return _the **number of strings** in_ `words` _that are a **prefix** of_ `s`.

A **prefix** of a string is a substring that occurs at the beginning of the string. A **substring** is a contiguous sequence of characters within a string.

**Example 1:**

**Input:** words = \[ "a ", "b ", "c ", "ab ", "bc ", "abc "\], s =  "abc "
**Output:** 3
**Explanation:**
The strings in words which are a prefix of s =  "abc " are:
 "a ",  "ab ", and  "abc ".
Thus the number of strings in words which are a prefix of s is 3.

**Example 2:**

**Input:** words = \[ "a ", "a "\], s =  "aa "
**Output:** 2
**Explanation:**
Both of the strings are a prefix of s. 
Note that the same string can occur multiple times in words, and it should be counted each time.

**Constraints:**

*   `1 <= words.length <= 1000`
*   `1 <= words[i].length, s.length <= 10`
*   `words[i]` and `s` consist of lowercase English letters **only**.
Minimum Average Difference

You are given a **0-indexed** integer array `nums` of length `n`.

The **average difference** of the index `i` is the **absolute** **difference** between the average of the **first** `i + 1` elements of `nums` and the average of the **last** `n - i - 1` elements. Both averages should be **rounded down** to the nearest integer.

Return _the index with the **minimum average difference**_. If there are multiple such indices, return the **smallest** one.

**Note:**

*   The **absolute difference** of two numbers is the absolute value of their difference.
*   The **average** of `n` elements is the **sum** of the `n` elements divided (**integer division**) by `n`.
*   The average of `0` elements is considered to be `0`.

**Example 1:**

**Input:** nums = \[2,5,3,9,5,3\]
**Output:** 3
**Explanation:**
- The average difference of index 0 is: |2 / 1 - (5 + 3 + 9 + 5 + 3) / 5| = |2 / 1 - 25 / 5| = |2 - 5| = 3.
- The average difference of index 1 is: |(2 + 5) / 2 - (3 + 9 + 5 + 3) / 4| = |7 / 2 - 20 / 4| = |3 - 5| = 2.
- The average difference of index 2 is: |(2 + 5 + 3) / 3 - (9 + 5 + 3) / 3| = |10 / 3 - 17 / 3| = |3 - 5| = 2.
- The average difference of index 3 is: |(2 + 5 + 3 + 9) / 4 - (5 + 3) / 2| = |19 / 4 - 8 / 2| = |4 - 4| = 0.
- The average difference of index 4 is: |(2 + 5 + 3 + 9 + 5) / 5 - 3 / 1| = |24 / 5 - 3 / 1| = |4 - 3| = 1.
- The average difference of index 5 is: |(2 + 5 + 3 + 9 + 5 + 3) / 6 - 0| = |27 / 6 - 0| = |4 - 0| = 4.
The average difference of index 3 is the minimum average difference so return 3.

**Example 2:**

**Input:** nums = \[0\]
**Output:** 0
**Explanation:**
The only index is 0 so return 0.
The average difference of index 0 is: |0 / 1 - 0| = |0 - 0| = 0.

**Constraints:**

*   `1 <= nums.length <= 105`
*   `0 <= nums[i] <= 105`
Count Unguarded Cells in the Grid

You are given two integers `m` and `n` representing a **0-indexed** `m x n` grid. You are also given two 2D integer arrays `guards` and `walls` where `guards[i] = [rowi, coli]` and `walls[j] = [rowj, colj]` represent the positions of the `ith` guard and `jth` wall respectively.

A guard can see **every** cell in the four cardinal directions (north, east, south, or west) starting from their position unless **obstructed** by a wall or another guard. A cell is **guarded** if there is **at least** one guard that can see it.

Return _the number of unoccupied cells that are **not** **guarded**._

**Example 1:**

**Input:** m = 4, n = 6, guards = \[\[0,0\],\[1,1\],\[2,3\]\], walls = \[\[0,1\],\[2,2\],\[1,4\]\]
**Output:** 7
**Explanation:** The guarded and unguarded cells are shown in red and green respectively in the above diagram.
There are a total of 7 unguarded cells, so we return 7.

**Example 2:**

**Input:** m = 3, n = 3, guards = \[\[1,1\]\], walls = \[\[0,1\],\[1,0\],\[2,1\],\[1,2\]\]
**Output:** 4
**Explanation:** The unguarded cells are shown in green in the above diagram.
There are a total of 4 unguarded cells, so we return 4.

**Constraints:**

*   `1 <= m, n <= 105`
*   `2 <= m * n <= 105`
*   `1 <= guards.length, walls.length <= 5 * 104`
*   `2 <= guards.length + walls.length <= m * n`
*   `guards[i].length == walls[j].length == 2`
*   `0 <= rowi, rowj < m`
*   `0 <= coli, colj < n`
*   All the positions in `guards` and `walls` are **unique**.
Escape the Spreading Fire

You are given a **0-indexed** 2D integer array `grid` of size `m x n` which represents a field. Each cell has one of three values:

*   `0` represents grass,
*   `1` represents fire,
*   `2` represents a wall that you and fire cannot pass through.

You are situated in the top-left cell, `(0, 0)`, and you want to travel to the safehouse at the bottom-right cell, `(m - 1, n - 1)`. Every minute, you may move to an **adjacent** grass cell. **After** your move, every fire cell will spread to all **adjacent** cells that are not walls.

Return _the **maximum** number of minutes that you can stay in your initial position before moving while still safely reaching the safehouse_. If this is impossible, return `-1`. If you can **always** reach the safehouse regardless of the minutes stayed, return `109`.

Note that even if the fire spreads to the safehouse immediately after you have reached it, it will be counted as safely reaching the safehouse.

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).

**Example 1:**

**Input:** grid = \[\[0,2,0,0,0,0,0\],\[0,0,0,2,2,1,0\],\[0,2,0,0,1,2,0\],\[0,0,2,2,2,0,2\],\[0,0,0,0,0,0,0\]\]
**Output:** 3
**Explanation:** The figure above shows the scenario where you stay in the initial position for 3 minutes.
You will still be able to safely reach the safehouse.
Staying for more than 3 minutes will not allow you to safely reach the safehouse.

**Example 2:**

**Input:** grid = \[\[0,0,0,0\],\[0,1,2,0\],\[0,2,0,0\]\]
**Output:** -1
**Explanation:** The figure above shows the scenario where you immediately move towards the safehouse.
Fire will spread to any cell you move towards and it is impossible to safely reach the safehouse.
Thus, -1 is returned.

**Example 3:**

**Input:** grid = \[\[0,0,0\],\[2,2,0\],\[1,2,0\]\]
**Output:** 1000000000
**Explanation:** The figure above shows the initial grid.
Notice that the fire is contained by walls and you will always be able to safely reach the safehouse.
Thus, 109 is returned.

**Constraints:**

*   `m == grid.length`
*   `n == grid[i].length`
*   `2 <= m, n <= 300`
*   `4 <= m * n <= 2 * 104`
*   `grid[i][j]` is either `0`, `1`, or `2`.
*   `grid[0][0] == grid[m - 1][n - 1] == 0`
Remove Digit From Number to Maximize Result

You are given a string `number` representing a **positive integer** and a character `digit`.

Return _the resulting string after removing **exactly one occurrence** of_ `digit` _from_ `number` _such that the value of the resulting string in **decimal** form is **maximized**_. The test cases are generated such that `digit` occurs at least once in `number`.

**Example 1:**

**Input:** number =  "123 ", digit =  "3 "
**Output:**  "12 "
**Explanation:** There is only one '3' in  "123 ". After removing '3', the result is  "12 ".

**Example 2:**

**Input:** number =  "1231 ", digit =  "1 "
**Output:**  "231 "
**Explanation:** We can remove the first '1' to get  "231 " or remove the second '1' to get  "123 ".
Since 231 > 123, we return  "231 ".

**Example 3:**

**Input:** number =  "551 ", digit =  "5 "
**Output:**  "51 "
**Explanation:** We can remove either the first or second '5' from  "551 ".
Both result in the string  "51 ".

**Constraints:**

*   `2 <= number.length <= 100`
*   `number` consists of digits from `'1'` to `'9'`.
*   `digit` is a digit from `'1'` to `'9'`.
*   `digit` occurs at least once in `number`.
Minimum Consecutive Cards to Pick Up

You are given an integer array `cards` where `cards[i]` represents the **value** of the `ith` card. A pair of cards are **matching** if the cards have the **same** value.

Return _the **minimum** number of **consecutive** cards you have to pick up to have a pair of **matching** cards among the picked cards._ If it is impossible to have matching cards, return `-1`.

**Example 1:**

**Input:** cards = \[3,4,2,3,4,7\]
**Output:** 4
**Explanation:** We can pick up the cards \[3,4,2,3\] which contain a matching pair of cards with value 3. Note that picking up the cards \[4,2,3,4\] is also optimal.

**Example 2:**

**Input:** cards = \[1,0,5,3\]
**Output:** -1
**Explanation:** There is no way to pick up a set of consecutive cards that contain a pair of matching cards.

**Constraints:**

*   `1 <= cards.length <= 105`
*   `0 <= cards[i] <= 106`
K Divisible Elements Subarrays

Given an integer array `nums` and two integers `k` and `p`, return _the number of **distinct subarrays** which have **at most**_ `k` _elements divisible by_ `p`.

Two arrays `nums1` and `nums2` are said to be **distinct** if:

*   They are of **different** lengths, or
*   There exists **at least** one index `i` where `nums1[i] != nums2[i]`.

A **subarray** is defined as a **non-empty** contiguous sequence of elements in an array.

**Example 1:**

**Input:** nums = \[**2**,3,3,**2**,**2**\], k = 2, p = 2
**Output:** 11
**Explanation:**
The elements at indices 0, 3, and 4 are divisible by p = 2.
The 11 distinct subarrays which have at most k = 2 elements divisible by 2 are:
\[2\], \[2,3\], \[2,3,3\], \[2,3,3,2\], \[3\], \[3,3\], \[3,3,2\], \[3,3,2,2\], \[3,2\], \[3,2,2\], and \[2,2\].
Note that the subarrays \[2\] and \[3\] occur more than once in nums, but they should each be counted only once.
The subarray \[2,3,3,2,2\] should not be counted because it has 3 elements that are divisible by 2.

**Example 2:**

**Input:** nums = \[1,2,3,4\], k = 4, p = 1
**Output:** 10
**Explanation:**
All element of nums are divisible by p = 1.
Also, every subarray of nums will have at most 4 elements that are divisible by 1.
Since all subarrays are distinct, the total number of subarrays satisfying all the constraints is 10.

**Constraints:**

*   `1 <= nums.length <= 200`
*   `1 <= nums[i], p <= 200`
*   `1 <= k <= nums.length`

**Follow up:**

Can you solve this problem in O(n2) time complexity?
Total Appeal of A String

The **appeal** of a string is the number of **distinct** characters found in the string.

*   For example, the appeal of `"abbca "` is `3` because it has `3` distinct characters: `'a'`, `'b'`, and `'c'`.

Given a string `s`, return _the **total appeal of all of its **substrings**.**_

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

**Example 1:**

**Input:** s =  "abbca "
**Output:** 28
**Explanation:** The following are the substrings of  "abbca ":
- Substrings of length 1:  "a ",  "b ",  "b ",  "c ",  "a " have an appeal of 1, 1, 1, 1, and 1 respectively. The sum is 5.
- Substrings of length 2:  "ab ",  "bb ",  "bc ",  "ca " have an appeal of 2, 1, 2, and 2 respectively. The sum is 7.
- Substrings of length 3:  "abb ",  "bbc ",  "bca " have an appeal of 2, 2, and 3 respectively. The sum is 7.
- Substrings of length 4:  "abbc ",  "bbca " have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 5:  "abbca " has an appeal of 3. The sum is 3.
The total sum is 5 + 7 + 7 + 6 + 3 = 28.

**Example 2:**

**Input:** s =  "code "
**Output:** 20
**Explanation:** The following are the substrings of  "code ":
- Substrings of length 1:  "c ",  "o ",  "d ",  "e " have an appeal of 1, 1, 1, and 1 respectively. The sum is 4.
- Substrings of length 2:  "co ",  "od ",  "de " have an appeal of 2, 2, and 2 respectively. The sum is 6.
- Substrings of length 3:  "cod ",  "ode " have an appeal of 3 and 3 respectively. The sum is 6.
- Substrings of length 4:  "code " has an appeal of 4. The sum is 4.
The total sum is 4 + 6 + 6 + 4 = 20.

**Constraints:**

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