Microsoft Online Assessment (OA) - Min Adj Swaps to Group Red Balls
There are N
balls positioned in a row. Each of them is either red
or white
. In one move we can swap two adjacent balls.
We want to arrange all the red balls into a consistent segment. What is the minimum number of swaps needed?
Given string S
of length N
built from characters "R"
and "W"
, representing red
and white
balls respectively,
returns the minimum number of swaps needed to arrange all the red balls into a consistent segment.
If the result exceeds 10^9
, return -1
.
Example 1:
Input:WRRWWR
Output: 2
Explanation:
We can move the last ball two positions to the left:
- swap
R
andW
->WRRWRW
- swap
R
andW
->WRRRWW
Example 2:
Input:WWRWWWRWR
Output: 4
Explanation:
We can move the last ball two positions to the left:
- swap
R
andW
->WWRWWWRRW
- swap
R
andW
->WWWRWWRRW
- swap
R
andW
->WWWWRWRRW
- swap
R
andW
->WWWWWRRRW
Example 3:
Input:WR
Output: -1
Explanation:
The minimum needed number of swaps is greater than 10^9
. So return -1
.
Example 4:
Input:WWW
Output: 0
Explanation:
There are no red balls to arrange into a segment.
Try it yourself
Implementation
1 | 1 |
| |
2 | - |
| |
2 | + |
| |
3 | + |
| |
4 | + | ||
5 | + |
| |
6 | + |
| |
7 | + |
| |
8 | + | ||
9 | + |
| |
10 | + |
| |
11 | + |
| |
12 | + |
| |
13 | + | ||
14 | + |
| |
15 | + |
| |
16 | + |
| |
17 | + |
| |
18 | + | ||
3 | 19 |
| |
4 | 20 |
|
Loading full content...