Largest Square Subgrid with Identical Letters

Given an integer (n) and an (n \times n) grid of characters, your task is to find the side length of the largest square subgrid where all the letters are identical. A common approach is to use dynamic programming. Define a DP table (dp[i][j]) such that if the character at position ((i, j)) is the same as the ones immediately above, left, and upper-left, then:

[ dp[i][j] = \min(dp[i-1][j],; dp[i][j-1],; dp[i-1][j-1]) + 1 ]

Otherwise, (dp[i][j] = 1). The answer is the maximum value in the DP table. This problem challenges your ability to properly iterate over the grid and handle boundary conditions.

inputFormat

The input is read from standard input (stdin) and consists of the following:

• The first line contains a single integer (n) (the size of the grid).
• The next (n) lines each contain a string of length (n) representing a row of the grid.

It is guaranteed that (1 \leq n \leq 1000) (for example) and each string consists of lowercase letters.

outputFormat

Print a single integer to standard output (stdout): the side length of the largest square subgrid in which all the letters are the same.## sample

4
aaaa
aabb
aabb
aabb

2