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