Python find the largest square in the matrix dynamic programming

It can be done with a complexity of O(n²) using dynamic programming. The idea is that you have a bigger square only when the up, the left and the up-left squares have the same dimension. Otherwise the max square of the current cell is just the smallest square among the squares considered above, increased by 1. Here is the code:

matrix = """
   ...o..o.o
   ...oo....
   ...o....o
   ..o.ooo..
   o........
   .oo......
   ..o....o.
   .oo......
   .........
"""

matrix = [list(r) for r in matrix.split()]
        
dp = [[0] * len(matrix) for _ in range(len(matrix))]
# max_square_dim, row, column
max_squares = [(0, None, None)]

for ri, r in enumerate(matrix):
    for ci, c in enumerate(r):
        dp[ri][ci] = 0 if c == 'o' \
            else (1 if ri == 0 or ci == 0 
            else min(dp[ri - 1][ci], dp[ri][ci - 1], dp[ri - 1][ci - 1]) + 1)
        
        max_squares = [(dp[ri][ci], ri, ci)] if dp[ri][ci] > max_squares[0][0] \
            else (max_squares + [(dp[ri][ci], ri, ci)] if dp[ri][ci] == max_squares[0][0]
            else max_squares)
            

for max_square in max_squares:
    for r in matrix[max_square[1] - max_square[0] + 1:max_square[1] + 1]:
        r[max_square[2] - max_square[0] + 1:max_square[2] + 1] = ['x'] * max_square[0]
      
result = '\n'.join([''.join(r) for r in matrix])
        
print(result)

In the end, when you have to replace the biggest square with all xs, you simply retrieve the indexes of the bottom-right vertex of the max square (stored in max_square) and do a list substitution.

EDIT: in case you have multiple biggest square, instead of declaring a single max_square, you have a list of them (in the update code I renamed it to max_squares). Then, every time you encounter a square with the same dimension as the max one, you just append it to the max_squares. However, consider the possibility of overlapping squares.