Palindromic Word Search

Time limit6sMemory limit1024 MB

Summary

Find the largest-area sub-rectangle of a letter grid that has a palindrome across one of its full rows and one of its full columns.

Level: Medium6 of 10
Topics: String matching, Matrix, Dynamic programming
Solved: No attempts yet

Problem

Given a rectangular grid of uppercase letters, find a rectangular region of the grid of maximum possible area such that there is a horizontal palindrome spanning some row of the rectangular region and a vertical palindrome spanning some column of the rectangular region. Recall a palindrome is a string that equals its own reversal.

Figure 1: Illustration of optimal solutions to the sample inputs. In the shaded subregions, a palindrome spanning an entire row of the region and a palindrome spanning an entire column of the region are highlighted.

Input

The first line contains two integers $R$ and $C$ ( $1 \leq R,C \leq 500$ ). The next $R$ lines describe the grid, each containing exactly $C$ uppercase letters.

Output

Output a single integer $A$ , the largest area of a rectangular region of the grid such that there is a horizontal palindrome spanning some row and a vertical palindrome spanning some column of the rectangular region.

Examples3

Example 1
Input
```
4 5
APPLE
BOBBY
KAYAK
REBEL
```
Expected output
```
15
```
Example 2
Input
```
2 6
ABCCDE
PRCDEE
```
Expected output
```
4
```
Example 3
Input
```
4 6
BANANA
BERGEN
CANNOT
FELLOW
```
Expected output
```
15
```