Flag
Contest: Codeforces Round 567 (Div. 2)
Difficulty rating: 1900
Tags: brute force, combinatorics, dp, implementation

Innokenty works at a flea market and sells some random stuff rare items. Recently he found an old rectangular blanket. It turned out that the blanket is split in $$$n \cdot m$$$ colored pieces that form a rectangle with $$$n$$$ rows and $$$m$$$ columns.

The colored pieces attracted Innokenty's attention so he immediately came up with the following business plan. If he cuts out a subrectangle consisting of three colored stripes, he can sell it as a flag of some country. Innokenty decided that a subrectangle is similar enough to a flag of some country if it consists of three stripes of equal heights placed one above another, where each stripe consists of cells of equal color. Of course, the color of the top stripe must be different from the color of the middle stripe; and the color of the middle stripe must be different from the color of the bottom stripe.

Innokenty has not yet decided what part he will cut out, but he is sure that the flag's boundaries should go along grid lines. Also, Innokenty won't rotate the blanket. Please help Innokenty and count the number of different subrectangles Innokenty can cut out and sell as a flag. Two subrectangles located in different places but forming the same flag are still considered different.

These subrectangles are flags.

These subrectangles are not flags.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 1\,000$$$) — the number of rows and the number of columns on the blanket.

Each of the next $$$n$$$ lines contains $$$m$$$ lowercase English letters from 'a' to 'z' and describes a row of the blanket. Equal letters correspond to equal colors, different letters correspond to different colors.

Output format:
In the only line print the number of subrectangles which form valid flags.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
The selected subrectangles are flags in the first example.

Example input:
4 3
aaa
bbb
ccb
ddd

Example output:
6

Example input:
6 1
a
a
b
b
c
c

Example output:
1

Editorial:
To start with, let's find a way to calculate the number of flags of width $$$1$$$.
Let's bruteforce the row $$$r$$$ and column $$$c$$$ of the topmost cell of the middle part of the flag.
So if the cell above has the same color as $$$(r, c)$$$ then clearly there can't be a flag here. Otherwise we are standing at the topmost position of the consecutive segment of cells of some color. Let's walk all this segment down and find its length $$$l$$$.
Note, that all mentioned above works in $$$\mathcal{O}(nm)$$$, since each cell would be walked exactly once. And now we can spend additional $$$\Theta(l)$$$ time to check whether there exist a unicolored segments of length $$$l$$$ above our segment and below our segment, the solution still works in $$$\mathcal{O}(nm)$$$.
So now we managed to find all "narrow" flags. The wide flag is simply a sequence of "narrow" flags of the common type (with the same value of $$$l$$$ and colors $$$color_1$$$, $$$color_2$$$, $$$color_3$$$ — color of the top, middle and bottom part of the flag).
Let's bruteforce the topmost row $$$r$$$ of the middle part of the flag. Now bruteforce $$$c$$$ and find a narrowflag as suggested above (there might be no flag in $$$(r, c)$$$ though). And also maintain $$$w$$$: a maximum possible length of the flag backwards. In case $$$(l, color_1, color_2, color_3)$$$ are same as in $$$(r, c - 1)$$$, then we increase $$$w$$$ by one. Otherwise assign $$$1$$$ to $$$w$$$.
Note that we in fact are iterating over all possible right-borders of the flag. And there are exactly $$$w$$$ possible left-borders. So we simply increase our answer by $$$w$$$ each time.