I couldn't get all test cases for this problem and it's driving me crazy. Please give it a jab if you have the time.
There is a board made of two rows and N columns. The board is represented by two strings, row1 and row2, made of characters 'R, W and/or '?'. A board is balanced if, in each row and in each column, the number of characters R' is equal to the number of characters 'W’. For example, the following board is balanced:
?RW?WR
?WR?RW
and the following board is not balanced:
W?WR?
R??W?
(there are two characters 'W' and one character 'R' in the first row).
The question marks (‘?') can be replaced with 'W’ or 'R'. What is the minimum number of replacements needed to balance the board?
Write a function:
def solution(row1, row2)
that, given two strings row and row made of N characters each, returns the minimum number of replacements needed to balance the board. If it is not possible to balance the board, the function should return -1.
Examples:
- For row1 = "W?WR?" and row2 = "R??W?", the board initially looks as follows:
W?WR?
R??W?
The last question mark in the first row and the second question mark in the second row can be replaced with 'R'. The last question mark in the second row can be replaced with 'w. After these replacements, the board is balanced and looks as follows:
W?WRR
R?RWW
The function should return 3.
- For row1 = "R?R??" and row2 = "??W??", five replacements are needed to balance the board:
R?RWW
W?WRR
The function should return 5.
- For row1 = "RR?" and row2 = "?R?", it is not possible to balance the board. The function should return -1.
- For row1 = "WWW??" and row2 = "RRR??", it is not possible to balance the board. The function should return -1.
- For row1 = "?RW?WR" and row2 = "?WR?RW", the board is already balanced. The function should return 0.
Write an efficient algorithm for the following assumptions:
• row1 and row2 are made only of the characters 'W', 'R' and/or'?';
• row1 and row have the same length, equal to N;
• N is an integer within the range [1..100,000).