Find the biggest rectangular area consisting only of 2 types of letter in a given MxN board.

Question

Possible duplicate: http://stackoverflow.com/questions/2301733

---

I need help with a problem.

Given a MxN board represented with M letters (a-z) in each of the N lines, i have to find the biggest area in which there are only 2 types of letters in it. The area must have rectangular shape. Here's an example :

4x4:

AAAA
ABBC
BBCA
DCAA

The output will be 6, because the biggest rectangular area in which there are only 2 types of letters is in the upper corner AAA-ABB, there are only A and B (2 types).

Answer 1

Not a complete working solution, but a possible direction to solving this problem:

Try representing the board in terms of connected regions, each region representing one or more connected locations containing the same letter. Then try to combine the regions.

Answer 2

Some ideas:

1. I think you will have to do an exhaustive search. However, once you have found a rectangle of area A that fits the criteria, there is no need to look at rectangles of any area less than A.

2. Any rectangle of size 2x2 or 1x3 that contains at least 3 different letters cannot be part of the solution. Perhaps you could "tag" those areas first, and then do a second scan through the input, only considering rectangles not including those tagged areas.

3. Find a 1x1 rectangle that fits the criteria (i.e., every cell). See if this rectangle can be expanded in one direction or the other and still fit the criteria. Continue until it cannot be expanded in either direction and still fit the criteria. There may be cases where the rectangle can be expanded in either direction: you will need to backtrack to check those cases (in your example, the 2x2 in the upper left can be expanded in either direction). This sounds like a search problem to me -- read up on some search techniques.