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 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, 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
18if __name__ == '__main__':
19    s = input()
20    res = min_swaps(s)
21    print(res)
22

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫