A game board consists of N+1 fields, numbered from 0 to N from left to right.
One letter ("a" or "b") is written between every two adjacent fields. The letters on the board are described by a string L of length N, where L[K] (for K within the range [0..N−1]) is the letter between fields K and K+1.
Example
For example, given L = "aaabab" and N = 6, the game board at the beginning looks like this:
a a a b a b
0 1 2 3 4 5 6
A game piece is placed at start. It can move left or right, flipping the letter it crosses ("a" -> "b" and "b" -> "a").
The objective is to find the minimum number of moves needed to balance the count of "a" and "b". If it's impossible, return -1.
Write a function that, given a string L of length N and an integer start, returns the minimum number of moves such that, after those moves, there will be the same number of letters "a" and "b" on the board (or returns −1 if it is impossible).
Examples
Input: L = "aaabab", start = 0
Explanation: The game piece must move one field to the right. This way, the first letter of L will be switched to produce string "baabab". Both letters occur three times in this string.
Output: 1
Input: L = "aaabab", start = 6
Explanation: The game piece has to move 5 times to the left:
"aaabab" -> "aaabab" -> "aaaaba" -> "aaabba" -> "aabbaa" -> "abbbaa"
Output: 5
Input: L = "abbba", start = 1
Explanation: It is impossible to equalize the number of letters "a" and "b".
Output: -1
Input: L = "bababa", start = 2
Explanation: The number of letters "a" and "b" is already equal.
Output: 0
Assumptions
- N is an integer within the range [1..100].
- L is made only of the characters 'a' and/or 'b'.
- start is an integer within the range [0..N].
A storeroom is used to organize items stored in it on N shelves. Shelves are numbered from 0 to N−1. The K-th shelf is dedicated to items of only one type, denoted by a positive integer A[K].
Recently it was decided that it is necessary to free R consecutive shelves. Shelves cannot be reordered. What is the maximum number of types of items that can still be stored in the storeroom after freeing R consecutive shelves?
Given:
- an array A of N integers representing types of items stored on storeroom shelves.
- an integer R representing the number of consecutive shelves to be freed.
Returns the maximum number of different types of items that can be stored in the storeroom after freeing R consecutive shelves.
Examples
Input: A = [2, 1, 2, 3, 2, 3, 2], R = 3
Explanation: It can be achieved by freeing shelves 2, 3, 4. The remaining shelves contain item types {2, 3}.
Output: 2
Input: A = [2, 3, 1, 1, 2], R = 2
Explanation: All three types (2, 3, 1) can still be stored by freeing the last two shelves.
Output: 3
Input: A = [20, 10, 10, 10, 30, 20], R = 3
Explanation: It can be achieved by freeing the first three shelves. The remaining item types are {10, 30, 20}.
Output: 3
Input: A = [1, 100000, 1], R = 3
Explanation: All shelves need to be freed, leaving no items.
Output: 0
Constraints
- N is an integer within the range [1..100,000].
- R is an integer within the range [1..N].
- Each element of array A is an integer within the range [1..1,000,000].
我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。
We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.
