Sonya and Matrix Beauty
Contest: Codeforces Round 524 (Div. 2)
Difficulty rating: 2400
Tags: strings

Sonya had a birthday recently. She was presented with the matrix of size $$$n\times m$$$ and consist of lowercase Latin letters. We assume that the rows are numbered by integers from $$$1$$$ to $$$n$$$ from bottom to top, and the columns are numbered from $$$1$$$ to $$$m$$$ from left to right.

Let's call a submatrix $$$(i_1, j_1, i_2, j_2)$$$ $$$(1\leq i_1\leq i_2\leq n; 1\leq j_1\leq j_2\leq m)$$$ elements $$$a_{ij}$$$ of this matrix, such that $$$i_1\leq i\leq i_2$$$ and $$$j_1\leq j\leq j_2$$$. Sonya states that a submatrix is beautiful if we can independently reorder the characters in each row (not in column) so that all rows and columns of this submatrix form palidroms.

Let's recall that a string is called palindrome if it reads the same from left to right and from right to left. For example, strings $$$abacaba, bcaacb, a$$$ are palindromes while strings $$$abca, acbba, ab$$$ are not.

Help Sonya to find the number of beautiful submatrixes. Submatrixes are different if there is an element that belongs to only one submatrix.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1\leq n, m\leq 250)$$$ — the matrix dimensions.

Each of the next $$$n$$$ lines contains $$$m$$$ lowercase Latin letters.

Output format:
Print one integer — the number of beautiful submatrixes.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Note:
In the first example, the following submatrixes are beautiful: $$$((1, 1), (1, 1)); ((1, 2), (1, 2));$$$ $$$((1, 3), (1, 3)); ((1, 1), (1, 3))$$$.

In the second example, all submatrixes that consist of one element and the following are beautiful: $$$((1, 1), (2, 1));$$$ $$$((1, 1), (1, 3)); ((2, 1), (2, 3)); ((1, 1), (2, 3)); ((2, 1), (2, 2))$$$.

Some of the beautiful submatrixes are: $$$((1, 1), (1, 5)); ((1, 2), (3, 4));$$$ $$$((1, 1), (3, 5))$$$.

The submatrix $$$((1, 1), (3, 5))$$$ is beautiful since it can be reordered as:

In such a matrix every row and every column form palindromes.

Example input:
1 3
aba

Example output:
4

Example input:
2 3
aca
aac

Example output:
11

Editorial:
Suppose we have a submatrix and we want to check whether it is beautiful. First, each line must have a maximum of one character that occurs an odd number of times. Why is this enough to ensure that each line can be made a palindrome by reordering the characters in it? If there is exactly one character that occurs an odd number of times, then the string has an odd length and we can swap it with characters that stand in the central position of the string. All remaining characters can be paired and placed in opposite positions relative to the center of the line. Obviously, this condition is necessary. Also, in order for the submatrix to be beautiful, the following property must be satisfied: the opposing lines of the submatrix, relative to the central lines, must have the same content of characters, possibly in a different order. In other words, if the number of the first line of the submatrix is ​​$$$i$$$, and the number of the last line of the submatrix is ​​$$$j$$$, then for any integer $$$k$$$ $$$(0 \leq k\leq j-i)$$$ and for any character $$$c$$$ from 'a' to 'z' should be true, that the number of times that the character $$$c$$$ occurs in the line with the number $$$i+k$$$ coincides with the number of times the character $$$c$$$ occurs in the line with the number $$$j-k$$$. The necessity of this condition is based on the fact that after reordering characters independently in each row, our columns should turn out to be palindromes. To better understand this, see the explanation of the third example from the problem statement.
Let us proceed to the solution of the problem: find the number of submatrices for which both of the above conditions are fulfilled. Fix the number of the first column of our submatrix. We will move the right column from the left one to the last one. So, what to do when we have two columns fixed. Let's define which strings can be palindromes, and which ones can't. To do this, we can support the auxiliary array $$$cnt[i][c]$$$ — how many times the character $$$c$$$ appears in the row with the number $$$i$$$. If the submatrix is ​​beautiful, then each of its rows can be a palindrome, which means we can break our lines into groups of maximum size from consecutive lines that can be palindromes, and solve the puzzle for each group independently.
Now we have the left and right columns of our submatrix, as well as a segment of consecutive lines, all of which can be palindromes. Then if we select any two rows and form a submatrix from these columns, rows and all rows between them, each row can be a palindrome, which means the first rule will always be fulfilled. It remains only to ensure that the second rule will be fulfilled.
Let's break all strings into equivalence classes. In other words, we will give each line some number that will characterize the content of this line — the number of times how many letters each occur in this line. If two lines coincide in content, then they will have the same equivalence class, otherwise their classes will be different. For example, if we have a set of $$$4$$$ lines $$${abac, ccab, bcaa, baab}$$$, then their classes will be $$${1, 2, 1, 3}$$$, respectively. How can you find these classes? Previously, we created an array of $$$cnt[i][c]$$$, which stores the number of occurrences of each character in each row. We can encode this array with a single number — hash. What to do when we find equivalence class for each line? Let's look at some sub-line from a row of lines. More precisely, we will be interested only in the sequence of their equivalence classes. If our submatrix (formed by all elements on this segment and between the fixed columns) is good, then the equivalence classes of opposite rows are equal. So the sequence of classes on this segment will be a palindrome. So, we reduced the task to finding the number of palindromes on some sequence. This can be done using the Manacher's algorithm for $$$O(n)$$$ for each fixed pair of columns, or for $$$O(nlogn)$$$ using binary search and one more auxiliary array of hashes.
More information about the mentioned topics can be found at the links listed below:
• Manacher's algorithm: https://cp-algorithms.com/string/manacher.html;
• Hashes: https://cp-algorithms.com/string/string-hashing.html;
• Equivalence classes: https://en.wikipedia.org/wiki/Equivalence_class;