How to find largest square of palindrome in a matrix

Question

I am trying to solve a problem where I am given a nXn square matrix of characters and I want to find out size of the largest palindrome square from this? The largest palindrome square is, a square with all rows and all columns as palindrome.

For eg. Input

a g h j k
s d g d j
s e f e n
a d g d h 
r y d g s

The output will be:

3

corresponding to the middle square. I am thinking of dynamic programming solution but unable to formulate the recurrence relation. I am thinking the dimensions should be a(i,j,k) where i, j are the bottom-right of rectangle and k be the size of palindrome square. Can someone help me with the recurrence relation for this problem?

EDIT:

n<500, so I believe that I can't go beyond O(n^3).

Answer 1

Assuming that you can solve the following problem:

• Ending at cell (i, j) is there any palindrome with different length horizontally and vertically.

Hint for above problem:

   boolean[][][]palindrome;//Is there any palindrome ending at (i , j) has length k
   for(int i = 0; i < n; i++){
       for(int j = 0; j < n; j++){
           palindrome[i][j][0] = true;
           palindrome[i][j][1] = true;
           for(int k = 2; k <= n; k++)
               if(data[i][j - k + 1] == data[i][j] && palindrome[i][j - 1][k - 2])
                  palindrome[i][j][k] = true; 
       } 
  }         

So, we can create two three dimensional arrays int[n][n][n]col and int[n][n][n]row.

For each cell(i, j), we will calculate the total number of palindrome with length k, ending at cell (0, j), (1, j) , ... (i, j) and total number of palindrome with length k, ending at cell (i,0), (i, 1), ... (i, j)

for(int k = 1; k <= n; k++)
    if(there is palindrome length k horizontally, end at cell (i, j)) 
       row[i][j][k] = 1 + row[i - 1][j][k];
    if(there is palindrome length k vertically, end at cell (i, j)) 
       col[i][j][k] = 1 + col[i][j - 1][k]; 

Finally, if row[i][j][k] >= k && col[i][j][k] >= k -> there is an square palindrome length k ending at (i,j).

In total, the time complexity will be O(n^3)

Answer 2

lets start with the complexity of validating a palindrome:

A palindrome can be identified in O(k) where k is the length of the palindrome see here

you then want need to do that test 2k times once for each row and column in you r inner square. (using the length of the palindrome k, as the dimension)

so now you have k * 2k -> O(2k^2) -> O(k^2)

then you want to increase the possible search space to the whole data set nxn this is when a 2nd variable gets introduced

you will need to iterate over columns 1 to (n-k) and all rows 1 to (n-k) in a nested loop.

so now you have (n-k)^2 * O(k^2) -> O(n^2 * k^2)

Note: this problem is dependant on more than one variable

This is the same approach i suggest you take to coding the solution, start small and get bigger

Answer 3

Im sure there is probably a better way, and im pretty sure my logic is correct so take this at face value as its not tested.

Just to make the example easy im going to say that i,j is the top left corner or coordinates 1,1

  1 2 3 4 5 6 7 8
1 a b c d e f g f 
2 d e f g h j k q 
3 a b g d z f g f 
4 a a a a a a a a

ie (1,1) = a, (1,5) = e and (2,1) = d

now instead of checking every column you could start by checking every kth column

ie when k=3

1) create a 2D boolean array the size of the character table all results TRUE

2) I start by checking column 3 cfg which is not a palindrome, thus I no longer need to test columns 1 or 2.

3) because the palindrome test failed marked the coresponding result in the 2D array (1,3) as FALSE (I know not to test any range that uses this position as it is not a palindrome)

4) Next check column 6, fjf which is a palindrome so I go back and test column 5, ehz != a palindrome

5) set (1,5) = FALSE

6) Then test column 8 then 7,

NOTE: You have only had to test 5 of the 8 columns.

since there were k columns in a row that were palindromes, now test the corresponding rows. Start from the bottom row in this case 3 as it will eliminate the most other checks if it fails

7) check row starting at (3,6) fgf = palindrome

8) check row starting at (2,6) jkq != a palindrome

9) set (2,6) = FALSE

10) check column starting at (2,3) daa != palindrome

11) set (2,3) = FALSE

Dont need to test any more for row 2 as both (2,3) and (2,6) are FALSE

Hopefully you can make sense of that.

Note: you would probably start this at k = n and decrement k until you find a result