ZOJ Problem Set - 4015
DreamGrid has a matrix \(A\) consisting of lowercase English letters. You are allowed to rearrange its rows any number of times (including zero times). Please calculate the maximum possible area of a submatrix in which every row and column is a palindromic string after the rearrangements.
Let's assume that the rows of matrix \(A\) are numbered from \(1\) to \(n\) from top to bottom and the columns are numbered from \(1\) to \(m\) from left to right. A matrix cell on the intersection of the \(i\)-th row and the \(j\)-th column can be represented as (\(i, j\)).
A palindromic string is a string that can be read the same way from left to right and from right to left. For example, "abacaba", "z", "abba" are palindromes.
A submatrix of matrix \(A\) is a group of four integers \(d, u, l, r\) (\(1 \le d \le u \le n, 1 \le l \le r \le m\)). The submatrix contains all the cells (\(i, j\)) satisfying both \(d \le i \le u\) and \(l \le j \le r\). The area of the submatrix is the number of cells it contains.
There are multiple test cases. The first line of input contains an integer \(T\), indicating the number of test cases. For each test case:
The first line contains two integers \(n\) and \(m\) (\(1 \le n \times m \le 2 \times 10^5\)) -- the number of rows and columns of the matrix.
Each of the next \(n\) lines contains \(m\) characters denoting the matrix.
It is guaranteed that the sum of \(n \times m\) in all cases does not exceed \(2 \times 10^6\).
For each test case, output an integer denoting the maximum possible area of a submatrix in which every row and column is a palindromic string after the rearrangements.
4 2 2 aa aa 3 3 aaa aaa bbb 3 3 abc def ghi 3 3 aba bab aba
4 9 1 9
Author: LIN, Xi
Source: The 18th Zhejiang University Programming Contest Sponsored by TuSimple