893. Groups of Special-Equivalent Strings
You are given an array of strings of the same length words.
In one move, you can swap any two even indexed characters or any two odd indexed characters of a string words[i].
Two strings words[i] and words[j] are special-equivalent if after any number of moves, words[i] == words[j].
- For example, words[i] = “zzxy” and words[j] = “xyzz” are special-equivalent because we may make the moves “zzxy” -> “xzzy” -> “xyzz”.
A group of special-equivalent strings from words is a non-empty subset of words such that:
- Every pair of strings in the group are special equivalent, and
- The group is the largest size possible (i.e., there is not a string words[i] not in the group such that words[i] is special-equivalent to every string in the group).
Return the number of groups of special-equivalent strings from words.
1357. Apply Discount Every n Orders
There is a supermarket that is frequented by many customers. The products sold at the supermarket are represented as two parallel integer arrays products and prices, where the ith product has an ID of products[i] and a price of prices[i].
When a customer is paying, their bill is represented as two parallel integer arrays product and amount, where the jth product they purchased has an ID of product[j], and amount[j] is how much of the product they bought. Their subtotal is calculated as the sum of each amount[j] * (price of the jth product).
The supermarket decided to have a sale. Every nth customer paying for their groceries will be given a percentage discount. The discount amount is given by discount, where they will be given discount percent off their subtotal. More formally, if their subtotal is bill, then they would actually pay bill * ((100 - discount) / 100).
Implement the Cashier class:
- Cashier(int n, int discount, int[] products, int[] prices) Initializes the object with n, the discount, and the products and their prices.
- double getBill(int[] product, int[] amount) Returns the final total of the bill with the discount applied (if any). Answers within 10-5 of the actual value will be accepted.
1947. Maximum Compatibility Score Sum
There is a survey that consists of n questions where each question’s answer is either 0 (no) or 1 (yes).
The survey was given to m students numbered from 0 to m - 1 and m mentors numbered from 0 to m - 1. The answers of the students are represented by a 2D integer array students where students[i] is an integer array that contains the answers of the ith student (0-indexed). The answers of the mentors are represented by a 2D integer array mentors where mentors[j] is an integer array that contains the answers of the jth mentor (0-indexed).
Each student will be assigned to one mentor, and each mentor will have one student assigned to them. The compatibility score of a student-mentor pair is the number of answers that are the same for both the student and the mentor.
- For example, if the student’s answers were [1, 0, 1] and the mentor’s answers were [0, 0, 1], then their compatibility score is 2 because only the second and the third answers are the same.
You are tasked with finding the optimal student-mentor pairings to maximize the sum of the compatibility scores.
Given students and mentors, return the maximum compatibility score sum that can be achieved.
1040. Moving Stones Until Consecutive II
There are some stones in different positions on the X-axis. You are given an integer array stones, the positions of the stones.
Call a stone an endpoint stone if it has the smallest or largest position. In one move, you pick up an endpoint stone and move it to an unoccupied position so that it is no longer an endpoint stone.
- In particular, if the stones are at say, stones = [1,2,5], you cannot move the endpoint stone at position 5, since moving it to any position (such as 0, or 3) will still keep that stone as an endpoint stone.
The game ends when you cannot make any more moves (i.e., the stones are in three consecutive positions).
Return an integer array answer of length 2 where:
- answer[0] is the minimum number of moves you can play, and
- answer[1] is the maximum number of moves you can play.
1810. Minimum Path Cost in a Hidden Grid
This is an interactive problem.
There is a robot in a hidden grid, and you are trying to get it from its starting cell to the target cell in this grid. The grid is of size m x n, and each cell in the grid is either empty or blocked. It is guaranteed that the starting cell and the target cell are different, and neither of them is blocked.
Each cell has a cost that you need to pay each time you move to the cell. The starting cell’s cost is not applied before the robot moves.
You want to find the minimum total cost to move the robot to the target cell. However, you do not know the grid’s dimensions, the starting cell, nor the target cell. You are only allowed to ask queries to the GridMaster object.
The GridMaster class has the following functions:
- boolean canMove(char direction) Returns true if the robot can move in that direction. Otherwise, it returns false.
- int move(char direction) Moves the robot in that direction and returns the cost of moving to that cell. If this move would move the robot to a blocked cell or off the grid, the move will be ignored, the robot will remain in the same position, and the function will return -1.
- boolean isTarget() Returns true if the robot is currently on the target cell. Otherwise, it returns false.
Note that direction in the above functions should be a character from {‘U’,’D’,’L’,’R’}, representing the directions up, down, left, and right, respectively.
Return the minimum total cost to get the robot from its initial starting cell to the target cell. If there is no valid path between the cells, return -1.
Custom testing:
The test input is read as a 2D matrix grid of size m x n and four integers r1, c1, r2, and c2 where:
- grid[i][j] == 0 indicates that the cell (i, j) is blocked.
- grid[i][j] >= 1 indicates that the cell (i, j) is empty and grid[i][j] is the cost to move to that cell.
- (r1, c1) is the starting cell of the robot.
- (r2, c2) is the target cell of the robot.
Remember that you will not have this information in your code.
There is a rectangular brick wall in front of you with n rows of bricks. The ith row has some number of bricks each of the same height (i.e., one unit) but they can be of different widths. The total width of each row is the same.
Draw a vertical line from the top to the bottom and cross the least bricks. If your line goes through the edge of a brick, then the brick is not considered as crossed. You cannot draw a line just along one of the two vertical edges of the wall, in which case the line will obviously cross no bricks.
Given the 2D array wall that contains the information about the wall, return the minimum number of crossed bricks after drawing such a vertical line.