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 repeated 100000 times.

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
+
    reds = []
3
-
    return 0
3
+
    for i, chr in enumerate(s):
4
+
        if chr == "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
+
4
18
if __name__ == '__main__':
5
19
    s = input()
6
20
    res = min_swaps(s)
7
21
    print(res)