Run DFS from corner cell. DFS can traverse in 8 directions. We can only traverse cells that are not marked with 'X'. Now, every time we visit a cell, we mark it as bad.

After the above step, only the cells that are marked with X or surrounded by 'X' characters will not be marked as 'bad'. We can then mark each of the non 'X' non-bad cells with a unique number, say 0.

Now our problem is reduced to finding the largest rectangle that contains only zeros.

This problem is solvable in O(n^3) using kadane algorithm to find the maximum sum rectangle in a 2-d grid. But since you were looking for a solution that is better than O(n^3), let's look at a better solution.

Assuming that the unique number that we used earlier is 0, we perform a horizontal sum of contiguous sequences of 0 in the grid. E.g.

0 0
0 0

becomes

1 1
2 2

Now, we can use the maximum area in a histogram subroutine to find the largest rectangle with only 0 inside. This solution works in O(n^2).

As I can understand O(N³) solution — you fix top-left corner of square, iterate over length of square, check in O(1) with prefix-sums if such square exists.

What we can observe that top-left and bottom-right corners of square lie on one main diagonal (x - y = const).

Let's calculate for each cell (x, y) next value:

value[x, y] = x + min(down[x, y], right[x, y]),

where down[x, y] — maximal length of vertical 'X' subsegment, started from (x, y) down,
right[x, y] — the same for horizontal subsegment, started right.

So let's process each main diagonal x - y = d separately.

For each vertex (x, x - d) we can calculate minX — the leftmost possible x of subsquare with (x, x - d) as bottom-right corner of it (can be done in O(1) with left[x, x - d] and up[x, x - d]).

We can make query "the minimal x0 that minX ≤ x0 ≤ x with value[x0, x0 - d] ≥ x" and try to update answer with square (x0, x0 - d) — (x, x - d)

This query can be done in O(logN) next way.

Construct segment tree, that can handle two queries:

1. set(index, value), where value is 0 or 1.
2. getLeftmostOne(left, right) — returns index of leftmost 1 at the segment (or -1, if segment contains only 0s).

There is algorithm of processing:

• At the start call set(x, 1) for each x.
• Create array of vectors where vector[x] contains all x0 such that value[x0, x0 - d] = x.
  
• Process all vertices in increasing order of x, after processing x = c for each x0 in vector[c] call set(x0, 0).
• Now our query can be done as 'get index of the leftmost 1 at the segment (minX, x)'.

Let's fix top-left corner of the square. We need to find the largest square with this corner. We can use binary search and check whether the square is filled, using prefix sums.

EDIT: sorry, misread