Loading...
Loading...
Loading...
A class rep draws a student's attendance as a ring of n cells, one per day, each marked P (present) or A (absent). Because it is a ring, the last cell sits next to the first cell.
For a poster, she wants all the P cells to form one unbroken block on the ring. In one swap she may exchange the marks of any two cells. Print the fewest swaps she needs. If the P cells already form one block, or there are no P cells, print 0.
P or A.Example 1
Input
PAPAAP
Output
1
Swap cells 2 and 3 to get PPAAAP. The last cell is next to the first, so PPP is one block on the ring.
Example 2
Input
PAPAPAPA
Output
2
Any block of 4 cells holds only 2 P, so 2 swaps are needed.
Try the problem first. Open one hint at a time.
If there are k cells marked P, the final block is some run of k neighbouring cells on the ring.
For a chosen block, every A inside it must be swapped with a P outside it, and one swap fixes exactly one such A. So the cost is the number of A cells in the block.
You want the run of k cells on the ring with the most P cells. Moving the run one cell forward adds one cell and drops one cell.
Handle the ring with index (start + k - 1) % n, and try all n starting cells.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor