Problem Statement
Elly's high-school class has equal number of boys and girls. For their graduation ceremony the headmaster asked them to get in order boy, girl, boy, girl, etc. However, before the beginning of the ceremony their order may be different (for example a group of boys may talk to each-other, then a group of girls and so on). If we represent the required order as a string "BGBGBG...BG" where 'B' represents a boy and 'G' represents a girl, their initial order may for example be "BBGGGBGBBBBGGBGG".
The ceremony is soon to start and now Elly wonders what is the minimal number of swaps of neighboring people that must occur in order for the girls and boys to get in the correct order. We consider two people "neighboring" if they are two consecutive letters in their order's string representation.
You are given the String initialOrder which gives the initial order of the children. Find the minimum number of swaps needed so the kids get in the required order.
The ceremony is soon to start and now Elly wonders what is the minimal number of swaps of neighboring people that must occur in order for the girls and boys to get in the correct order. We consider two people "neighboring" if they are two consecutive letters in their order's string representation.
You are given the String initialOrder which gives the initial order of the children. Find the minimum number of swaps needed so the kids get in the required order.
Definition
- Class:
- EllysBoysAndGirls
- Method:
- getSwaps
- Parameters:
- String
- Returns:
- int
- Method signature:
- int getSwaps(String initialOrder)
- (be sure your method is public)
Constraints
- initialOrder will contain between 2 and 100 characters, inclusive.
- Each character of initialOrder will be either 'B' or 'G'.
- initialOrder will contain equal number of 'B'-s and 'G'-s. (This implies that initialOrder will contain an even number of characters.)
Examples
"BBGGGBGBBBBGGBGG"
Returns: 7
The correct order is reached by doing the following swaps (all indexes are 0-based): Swap the boy at index 1 with the girl at index 2; Swap the girl at index 4 with the boy at index 5; Swap the girl at index 6 with the boy at index 7; Move the girl at index 11 to index 9 (using 2 swaps); Swap the girl at index 12 with the boy which just came to index 11; Swap the boy at index 13 with the girl at index 14;"BGBG"
Returns: 0
The boys and girls are already in the correct order."GGGGGGGGGGBBBBBBBBBB"
Returns: 55
Sometimes many swaps may be needed."GGBBBBGGGBBBGBBGBBBGGGGBBGGBBBGBBGBGBBGGGGGBGG"
Returns: 48
Back to all problems