Swap and Explore
All submissions for this problem are available.
Rob likes to explore but is lazy.
He has many cubes arranged before him in a line. Each cube has either the letter 'A' or 'B' inscribed on it.
Now Rob wants to swap any two positions of cubes placed on the line, such that the there exists a sequence of continuous cubes with letter 'A' inscribed on them, whose number is greater than or equal to M.
However, mechanically swapping cubes is a tedious task. Therefore he wishes to know the minimum number of swap operations he has to perform to get such an arrangement of cubes.
First line consists of T test cases.
For each test case, first line consists of the string S, composed of A's and B's, representing the initial configuration of cubes, and second line an integer M.
The output consists of T lines corresponding to T test cases, such that it is the minimum number of operations required to create a consecutive segment of greater than M A’s from S.
- 1 ≤ Sum of lengths of S over all test cases ≤ 106
- 1 ≤ Length(S) ≤ 105
- It is ensured that number of A's are >= M.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 4.9.2, GO, JAVA|
Fetching successful submissions