https://leetcode.com/problems/interleaving-string/

97. Interleaving String
Medium
6.8K
411
Companies

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

An interleaving of two strings s and t is a configuration where s and t are divided into n and m
substrings
respectively, such that:

s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
The interleaving is s1 + t1 + s2 + t2 + s3 + t3 + ... or t1 + s1 + t2 + s2 + t3 + s3 + ...

Note: a + b is the concatenation of strings a and b.



Example 1:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".
Since s3 can be obtained by interleaving s1 and s2, we return true.

Example 2:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
Output: false
Explanation: Notice how it is impossible to interleave s2 with any other string to obtain s3.

Example 3:

Input: s1 = "", s2 = "", s3 = ""
Output: true



Constraints:

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1, s2, and s3 consist of lowercase English letters.



Follow up: Could you solve it using only O(s2.length) additional memory space?

https://leetcode.com/problems/maximum-length-of-pair-chain/

646. Maximum Length of Pair Chain
Medium
3.3K
118
Companies

You are given an array of n pairs pairs where pairs[i] = [lefti, righti] and lefti < righti.

A pair p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this fashion.

Return the length longest chain which can be formed.

You do not need to use up all the given intervals. You can select pairs in any order.



Example 1:

Input: pairs = [[1,2],[2,3],[3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4].

Example 2:

Input: pairs = [[1,2],[7,8],[4,5]]
Output: 3
Explanation: The longest chain is [1,2] -> [4,5] -> [7,8].



Constraints:

n == pairs.length
1 <= n <= 1000
-1000 <= lefti < righti <= 1000

https://leetcode.com/problems/frog-jump/

403. Frog Jump
Hard
4.2K
204
Companies

A frog is crossing a river. The river is divided into some number of units, and at each unit, there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.

Given a list of stones' positions (in units) in sorted ascending order, determine if the frog can cross the river by landing on the last stone. Initially, the frog is on the first stone and assumes the first jump must be 1 unit.

If the frog's last jump was k units, its next jump must be either k - 1, k, or k + 1 units. The frog can only jump in the forward direction.



Example 1:

Input: stones = [0,1,3,5,6,8,12,17]
Output: true
Explanation: The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.

Example 2:

Input: stones = [0,1,2,3,4,8,9,11]
Output: false
Explanation: There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.



Constraints:

2 <= stones.length <= 2000
0 <= stones[i] <= 231 - 1
stones[0] == 0
stones is sorted in a strictly increasing order.

https://leetcode.com/problems/implement-stack-using-queues/

225. Implement Stack using Queues
Easy
4.9K
1K
Companies

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.



Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False



Constraints:

1 <= x <= 9
At most 100 calls will be made to push, pop, top, and empty.
All the calls to pop and top are valid.



Follow-up: Can you implement the stack using only one queue?

https://leetcode.com/problems/minimum-penalty-for-a-shop/

2483. Minimum Penalty for a Shop
Medium
471
21
Companies

You are given the customer visit log of a shop represented by a 0-indexed string customers consisting only of characters 'N' and 'Y':

if the ith character is 'Y', it means that customers come at the ith hour
whereas 'N' indicates that no customers come at the ith hour.

If the shop closes at the jth hour (0 <= j <= n), the penalty is calculated as follows:

For every hour when the shop is open and no customers come, the penalty increases by 1.
For every hour when the shop is closed and customers come, the penalty increases by 1.

Return the earliest hour at which the shop must be closed to incur a minimum penalty.

Note that if a shop closes at the jth hour, it means the shop is closed at the hour j.



Example 1:

Input: customers = "YYNY"
Output: 2
Explanation:
- Closing the shop at the 0th hour incurs in 1+1+0+1 = 3 penalty.
- Closing the shop at the 1st hour incurs in 0+1+0+1 = 2 penalty.
- Closing the shop at the 2nd hour incurs in 0+0+0+1 = 1 penalty.
- Closing the shop at the 3rd hour incurs in 0+0+1+1 = 2 penalty.
- Closing the shop at the 4th hour incurs in 0+0+1+0 = 1 penalty.
Closing the shop at 2nd or 4th hour gives a minimum penalty. Since 2 is earlier, the optimal closing time is 2.

Example 2:

Input: customers = "NNNNN"
Output: 0
Explanation: It is best to close the shop at the 0th hour as no customers arrive.

Example 3:

Input: customers = "YYYY"
Output: 4
Explanation: It is best to close the shop at the 4th hour as customers arrive at each hour.



Constraints:

1 <= customers.length <= 10^5
customers consists only of characters 'Y' and 'N'.

https://leetcode.com/problems/minimum-replacements-to-sort-the-array/description/

2366. Minimum Replacements to Sort the Array
Hard
833
27
Companies

You are given a 0-indexed integer array nums. In one operation you can replace any element of the array with any two elements that sum to it.

For example, consider nums = [5,6,7]. In one operation, we can replace nums[1] with 2 and 4 and convert nums to [5,2,4,7].

Return the minimum number of operations to make an array that is sorted in non-decreasing order.



Example 1:

Input: nums = [3,9,3]
Output: 2
Explanation: Here are the steps to sort the array in non-decreasing order:
- From [3,9,3], replace the 9 with 3 and 6 so the array becomes [3,3,6,3]
- From [3,3,6,3], replace the 6 with 3 and 3 so the array becomes [3,3,3,3,3]
There are 2 steps to sort the array in non-decreasing order. Therefore, we return 2.

Example 2:

Input: nums = [1,2,3,4,5]
Output: 0
Explanation: The array is already in non-decreasing order. Therefore, we return 0.



Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9

https://leetcode.com/problems/minimum-number-of-taps-to-open-to-water-a-garden/

1326. Minimum Number of Taps to Open to Water a Garden
Hard
2.2K
127
Companies

There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).

There are n + 1 taps located at points [0, 1, ..., n] in the garden.

Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.

Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.



Example 1:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]

Example 2:

Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.



Constraints:

1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100

https://leetcode.com/problems/counting-bits/

338. Counting Bits
Easy
9.5K
449
Companies

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.



Example 1:

Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10

Example 2:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101



Constraints:

0 <= n <= 10^5



Follow up:

It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass?
Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

https://leetcode.com/problems/extra-characters-in-a-string/

2707. Extra Characters in a String
Medium
600
36
Companies

You are given a 0-indexed string s and a dictionary of words dictionary. You have to break s into one or more non-overlapping substrings such that each substring is present in dictionary. There may be some extra characters in s which are not present in any of the substrings.

Return the minimum number of extra characters left over if you break up s optimally.



Example 1:

Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
Output: 1
Explanation: We can break s in two substrings: "leet" from index 0 to 3 and "code" from index 5 to 8. There is only 1 unused character (at index 4), so we return 1.

Example 2:

Input: s = "sayhelloworld", dictionary = ["hello","world"]
Output: 3
Explanation: We can break s in two substrings: "hello" from index 3 to 7 and "world" from index 8 to 12. The characters at indices 0, 1, 2 are not used in any substring and thus are considered as extra characters. Hence, we return 3.



Constraints:

1 <= s.length <= 50
1 <= dictionary.length <= 50
1 <= dictionary[i].length <= 50
dictionary[i] and s consists of only lowercase English letters
dictionary contains distinct words

https://leetcode.com/problems/unique-paths/

62. Unique Paths
Medium
15K
405
Companies

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.



Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down



Constraints:

1 <= m, n <= 100

### Problem

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

### Example

Example 1:

Input: head = [3,2,0,-4], pos = 1

Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0

Output: true

Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1

Output: false

Explanation: There is no cycle in the linked list.

### Constraints

- The number of nodes in the list is in the range [0, 104].
- -105 <= Node.val <= 105
- pos is -1 or a valid index in the linked list.

### Follow up

Can you solve it using O(1) (i.e. constant) memory?

### Additional Information

Problem URL: [https://leetcode.com/problems/linked-list-cycle/?envType=daily-question&amp;envId=2023-09-04](https://leetcode.com/problems/linked-list-cycle/?envType=daily-question&amp;envId=2023-09-04)

Problem Description

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

Input

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:
- val: an integer representing Node.val
- random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Output

Return the head of the copied linked list.

Examples

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Constraints

0 <= n <= 1000
-104 <= Node.val <= 104
Node.random is null or is pointing to some node in the linked list.

Problem URL

The problem can be found at: [Copy List with Random Pointer](https://leetcode.com/problems/copy-list-with-random-pointer/?envType=daily-question&amp;envId=2023-09-05)

Problem Description:

Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts. The length of each part should be as equal as possible, with no two parts having a size differing by more than one. This may lead to some parts being null. The parts should be in the order of occurrence in the input list, with parts occurring earlier always having a size greater than or equal to parts occurring later. Return an array of the k parts.

Example 1:

Input:
head = [1,2,3]
k = 5

Output:
[[1],[2],[3],[],[]]

Explanation:
The first element (output[0]) has value 1 and next node as null. The last element (output[4]) is null, but its string representation as a ListNode is [].

Example 2:

Input:
head = [1,2,3,4,5,6,7,8,9,10]
k = 3

Output:
[[1,2,3,4],[5,6,7],[8,9,10]]

Explanation:
The input has been split into consecutive parts with a size difference at most 1, and earlier parts are larger in size than the later parts.

Constraints:

- The number of nodes in the list is in the range [0, 1000].
- 0 <= Node.val <= 1000
- 1 <= k <= 50
https://leetcode.com/problems/split-linked-list-in-parts/?envType=daily-question&amp;envId=2023-09-06

[Problem url](https://leetcode.com/problems/reverse-linked-list-ii/?envType=daily-question&amp;envId=2023-09-07)

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:
Input: head = [5], left = 1, right = 1
Output: [5]

Constraints:
The number of nodes in the list is n.
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

Follow up: Could you do it in one pass?

Problem url: [https://leetcode.com/problems/pascals-triangle/?envType=daily-question&amp;envId=2023-09-08]

Description:
Given an integer numRows, return the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example 1:
Input: numRows = 5
Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Example 2:
Input: numRows = 1
Output: [[1]]

Constraints:
1 <= numRows <= 30

Problem URL: [Combination Sum IV - LeetCode](https://leetcode.com/problems/combination-sum-iv/?envType=daily-question&amp;envId=2023-09-09)

Problem Statement:
Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to the target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.

Example 2:

Input: nums = [9], target = 3
Output: 0

Constraints:
- 1 <= nums.length <= 200
- 1 <= nums[i] <= 1000
- All the elements of nums are unique.
- 1 <= target <= 1000

Problem Description

Given a number n representing the total number of orders, where each order consists of a pickup and a delivery service. Count all the valid sequences of pickup and delivery such that the delivery for each order always comes after the pickup. Since the answer may be large, return it modulo 10^9 + 7.

Examples

Example 1:

Input: n = 1
Output: 1
Explanation: There is only one unique order (P1, D1), where Delivery 1 always comes after Pickup 1.

Example 2:

Input: n = 2
Output: 6
Explanation: There are six possible orders:
1. (P1, P2, D1, D2)
2. (P1, P2, D2, D1)
3. (P1, D1, P2, D2)
4. (P2, P1, D1, D2)
5. (P2, P1, D2, D1)
6. (P2, D2, P1, D1)
However, the order (P1, D2, P2, D1) is invalid because Pickup 2 comes after Delivery 2.

Example 3:

Input: n = 3
Output: 90

Constraints:

1 <= n <= 500

Problem URL

The problem can be found [here](https://leetcode.com/problems/count-all-valid-pickup-and-delivery-options/?envType=daily-question&amp;envId=2023-09-10).

Problem URL: [Group the People Given the Group Size They Belong To - LeetCode](https://leetcode.com/problems/group-the-people-given-the-group-size-they-belong-to/?envType=daily-question&amp;envId=2023-09-11)

Description:

- There are n people that are split into some unknown number of groups.
- Each person is labeled with a unique ID from 0 to n - 1.
- You are given an integer array groupSizes, where groupSizes[i] is the size of the group that person i is in.
- Return a list of groups such that each person i is in a group of size groupSizes[i].
- Each person should appear in exactly one group, and every person must be in a group.
- If there are multiple answers, return any of them.
- It is guaranteed that there will be at least one valid solution for the given input.

Examples:

Example 1:

Input:

groupSizes = [3,3,3,3,3,1,3]

Output:

[[5],[0,1,2],[3,4,6]]

Explanation:
- The first group is [5]. The size is 1, and groupSizes[5] = 1.
- The second group is [0,1,2]. The size is 3, and groupSizes[0] = groupSizes[1] = groupSizes[2] = 3.
- The third group is [3,4,6]. The size is 3, and groupSizes[3] = groupSizes[4] = groupSizes[6] = 3.
- Other possible solutions are [[2,1,6],[5],[0,4,3]] and [[5],[0,6,2],[4,3,1]].

Example 2:

Input:

groupSizes = [2,1,3,3,3,2]

Output:

[[1],[0,5],[2,3,4]]

Constraints:

- groupSizes.length == n
- 1 <= n <= 500
- 1 <= groupSizes[i] <= n

Problem Description

A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, we need to find the minimum number of characters we need to delete to make s good.

The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

Example 1

Input: s = "aab"
Output: 0
Explanation: s is already good.

Example 2

Input: s = "aaabbbcc"
Output: 2
Explanation: You can delete two 'b's resulting in the good string "aaabcc". Another way is to delete one 'b' and one 'c' resulting in the good string "aaabbc".

Example 3

Input: s = "ceabaacb"
Output: 2
Explanation: You can delete both 'c's resulting in the good string "eabaab". Note that we only care about characters that are still in the string at the end (i.e. frequency of 0 is ignored).

Constraints

- 1 <= s.length <= 10^5
- s contains only lowercase English letters.

[Problem URL](https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/?envType=daily-question&amp;envId=2023-09-12)

Problem url: [https://leetcode.com/problems/candy/?envType=daily-question&amp;envId=2023-09-13]

Problem:
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second, and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second, and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

Constraints:
- n == ratings.length
- 1 <= n <= 2 * 10^4
- 0 <= ratings[i] <= 2 * 10^4

Problem: Reconstruct Itinerary

URL: [Problem URL](https://leetcode.com/problems/reconstruct-itinerary/?envType=daily-question&amp;envId=2023-09-14)

Description:
- Given a list of airline tickets where each ticket represents the departure and arrival airports of a flight.
- Reconstruct the itinerary in order and return it.
- All tickets belong to a man who departs from "JFK".
- The itinerary must begin with "JFK".
- If multiple valid itineraries exist, return the one with the smallest lexical order.
- All tickets must be used once and only once.

Examples:
1. Input: [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

2. Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"] but it is larger in lexical order.

Constraints:
- 1 <= tickets.length <= 300
- tickets[i].length == 2
- fromi.length == 3
- toi.length == 3
- fromi and toi consist of uppercase English letters.
- fromi != toi