Given a string rectangular board which is divided into unit cells. Each cell is initially painted black or white. The character board[i][j] represents the cell with coordinates (i, j). Each of those characters is either 'B' (representing a black cell) or 'W' (representing a white cell). The game is played in turns.
In each turn player can choose any row of the board and repaint all black cells of the row to white, and vice versa. (Note that he can only select rows, not columns. Formally, he can choose an index i and change all characters of board[i].)
Now he wants to have a large white square somewhere on his board. The sides of square must be parallel to the sides of the board. The white square may be a part of a larger white area. (I.e., the cells that touch the square may be both black and white.) Find a sequence of turns that produces the largest possible white square somewhere on the board, and return the area of that square.
EXAMPLE :
WBBB
WBBB
WWWW
Returns: 9
We should repaint row 0 and then repaint row 1. The resulting board will contain a 3*3 white square (in rows 0-2 and columns 1-3).
Let the board size be $m \times n$. Below is a very simple solution that runs in $O(mn^2)$ time. There should be a faster algorithm but I'm lazy to try to find it.
We are looking for an optimal solution among a set of valid solutions, so we should try different ways of parametrizing the valid solutions. One way is by their (left,right) coordinates. There are $O(n^2)$ such pairs. For each pair, any valid rectangle must correspond to a consecutive set of row segments that are all the same colour from the specified left to right, which we shall call valid (left,right) segments. There are $m$ row segments we need to consider, and if we first compute all their validities, it reduces to finding a longest substring of ones in a binary sequence, which gives us a largest rectangle with specified left and right.