Rarity and New Dress
Carousel Boutique is busy again! Rarity has decided to visit the pony ball and she surely needs a new dress, because going out in the same dress several times is a sign of bad manners. First of all, she needs a dress pattern, which she is going to cut out from the rectangular piece of the multicolored fabric.The piece of the multicolored fabric consists of $$$n \times m$$$ separate square scraps. Since Rarity likes dresses in style, a dress pattern must only include scraps sharing the same color. A dress pattern must be the square, and since Rarity is fond of rhombuses, the sides of a pattern must form a $$$45^{\circ}$$$ angle with sides of a piece of fabric (that way it will be resembling the traditional picture of a rhombus).Examples of proper dress patterns:  Examples of improper dress patterns:  The first one consists of multi-colored scraps, the second one goes beyond the bounds of the piece of fabric, the third one is not a square with sides forming a $$$45^{\circ}$$$ angle with sides of the piece of fabric.Rarity wonders how many ways to cut out a dress pattern that satisfies all the conditions that do exist. Please help her and satisfy her curiosity so she can continue working on her new masterpiece!
In the first example, all the dress patterns of size $$$1$$$ and one of size $$$2$$$ are satisfactory.In the second example, only the dress patterns of size $$$1$$$ are satisfactory.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2000$$$). Each of the next $$$n$$$ lines contains $$$m$$$ characters: lowercase English letters, the $$$j$$$-th of which corresponds to scrap in the current line and in the $$$j$$$-th column. Scraps having the same letter share the same color, scraps having different letters have different colors.
Print a single integer: the number of ways to cut out a dress pattern to satisfy all of Rarity's conditions.
import io
import os
from array import array
ordA = ord('a')

def solve(R, C, grid):
    seen = [False for i in range(26)]
    for i in range(R * C):
        seen[grid[i] - ordA] = True
    ans = 0
    CC = C + 1
    dp2 = array('h', (0 for i in range(CC)))
    dp1 = array('h', (0 for i in range(CC)))
    dp0 = array('h', (0 for i in range(CC)))
    for i in range(26):
        ch = ordA + i
        if seen[i]:
            for c in range(C):
                dp2[c] = 0
                dp1[c] = 0
            j = 0
            for r in range(R):
                for c in range(C):
                    dp0[c] = 0 if grid[j] != ch else 1 + min(dp2[c], dp1[c - 1], dp1[c], dp1[c + 1])
                    ans += dp0[c]
                    j += 1
                (dp2, dp1, dp0) = (dp1, dp0, dp2)
    return ans

def solve(R, C, grid):
    ans = 0
    CC = C + 1
    dp2 = array('h', (0 for i in range(CC)))
    dp1 = array('h', (0 for i in range(CC)))
    dp0 = array('h', (0 for i in range(CC)))
    for r in range(R):
        for c in range(C):
            ch = grid[r * C + c]
            dp0[c] = 1
            if r >= 2 and 0 < c < C - 1 and (grid[(r - 2) * C + c] == grid[(r - 1) * C + c - 1] == grid[(r - 1) * C + c] == grid[(r - 1) * C + c + 1] == ch):
                dp0[c] = 1 + min(dp2[c], dp1[c - 1], dp1[c], dp1[c + 1])
            ans += dp0[c]
        (dp2, dp1, dp0) = (dp1, dp0, dp2)
    return ans
if __name__ == '__main__':
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
    (N, M) = [int(x) for x in input().split()]
    grid = b''.join((input().rstrip() for i in range(N)))
    ans = solve(N, M, grid)
    print(ans)
import os
import sys
from io import BytesIO, IOBase
import threading
from collections import defaultdict
import heapq
from math import ceil, floor

def main():
    ans = 0
    (n, m) = map(int, input().split())
    dp = [[0] * m for i in range(n)]
    ans = 0
    s = []
    for i in range(n):
        s.append(input())
        for j in range(m):
            dp[i][j] = 1
            if i >= 2 and 0 < j < m - 1:
                if s[i][j] == s[i - 1][j - 1] == s[i - 1][j + 1] == s[i - 2][j] == s[i - 1][j]:
                    dp[i][j] += min(dp[i - 1][j - 1], dp[i - 1][j + 1], dp[i - 2][j])
            ans += dp[i][j]
    print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
if __name__ == '__main__':
    for i in range(1):
        main()
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, m) = map(int, input().split())
dp1 = []
dp0 = [0] * m
s = []
s0 = [0] * m
for i in range(n):
    dp = [0] * m
    s1 = list(input().rstrip())
    (c, w) = (0, s1[0])
    for j in range(m):
        if s1[j] ^ w:
            w = s1[j]
            c = 0
        c += 1
        dp[j] = c
    (c, w) = (0, s1[-1])
    for j in range(m - 1, -1, -1):
        if s1[j] ^ w:
            w = s1[j]
            c = 0
        c += 1
        if s0[j] ^ s1[j]:
            dp[j] = 1
        else:
            dp[j] = min(dp[j], c, dp0[j] + 1)
    dp1.append(list(dp))
    dp0 = dp
    s.append(list(s1))
    s0 = s1
dp0 = [0] * m
s0 = [0] * m
ans = 0
for i in range(n - 1, -1, -1):
    dp = [0] * m
    s1 = s[i]
    (c, w) = (0, s1[0])
    for j in range(m):
        if s1[j] ^ w:
            w = s1[j]
            c = 0
        c += 1
        dp[j] = c
    (c, w) = (0, s1[-1])
    for j in range(m - 1, -1, -1):
        if s1[j] ^ w:
            w = s1[j]
            c = 0
        c += 1
        if s0[j] ^ s1[j]:
            dp[j] = 1
        else:
            dp[j] = min(dp[j], c, dp0[j] + 1)
    for (j, k) in zip(dp, dp1[i]):
        ans += min(j, k)
    dp0 = dp
    s0 = s1
print(ans)