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
RandW->WRRWRW - swap
RandW->WRRRWW
Example 2:
Input:WWRWWWRWR
Output: 4
Explanation:
We can move the last ball two positions to the left:
- swap
RandW->WWRWWWRRW - swap
RandW->WWWRWWRRW - swap
RandW->WWWWRWRRW - swap
RandW->WWWWWRRRW
Example 3:
Input:WR repeated 100000 times.
Output: -1
Explanation:
The minimum number of swaps needed 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
1def min_swaps(s: str) -> int:
2 reds = []
3 for i, c in enumerate(s):
4 if c == "R":
5 reds.append(i)
6 n = len(reds)
7 if n == 0:
8 return 0
9 start_ptr = 0
10 end_ptr = n - 1
11 count = 0
12 while start_ptr < end_ptr:
13 count += reds[end_ptr] - reds[start_ptr] - end_ptr + start_ptr
14 start_ptr += 1
15 end_ptr -= 1
16 return -1 if count > 10**9 else count
17
18if __name__ == "__main__":
19 s = input()
20 res = min_swaps(s)
21 print(res)
22