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 and W -> WRRWRW
  • swap R and W -> WRRRWW

Example 2:

Input:WWRWWWRWR

Output: 4

Explanation:

We can move the last ball two positions to the left:

  • swap R and W -> WWRWWWRRW
  • swap R and W -> WWWRWWRRW
  • swap R and W -> WWWWRWRRW
  • swap R and W -> 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
def min_swaps(s: str) -> int:
2
-
    # WRITE YOUR BRILLIANT CODE HERE
2
+
    count = 0
3
-
    return 0
3
+
    swaps = 0
4
4
5
5
6
+
    if 'R' not in s:
7
+
        return 0
8
+
    first = s.index('R')
9
+
10
+
    for i in range(len(s)):
11
+
        if s[i] == 'R':
12
+
            swaps += 1
13
+
            count = i
14
+
15
+
    return -1 if count == first else count - first - swaps + 1
16
+
6
17
if __name__ == '__main__':
7
18
    s = input()
8
19
    res = min_swaps(s)
9
20
    print(res)