Flag (Codeforces 1181C)
Tags: Implement, combinatorics

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: 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: In the only line print the number of subrectangles which form valid flags.

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

Sample Inputs:
4 3
aaa
bbb
ccb
ddd

6 1
a
a
b
b
c
c

Sample Outputs:
6

1

Solution (Python):
def naiveSolve():
    return

def solve():
    return

def main():
    (n, m) = readIntArr()
    grid = []
    for _ in range(n):
        grid.append(input())
    same = [[1 for _ in range(m)] for __ in range(n)]
    for i in range(n - 2, -1, -1):
        for j in range(m):
            if grid[i][j] == grid[i + 1][j]:
                same[i][j] = same[i + 1][j] + 1
    ans = 0
    for i in range(n):
        prevThickness = -1
        prevLen = 0
        for j in range(m):
            currThickness = same[i][j]
            i2 = i + currThickness
            i3 = i2 + currThickness
            if i3 >= n or not (currThickness == same[i2][j] and currThickness <= same[i3][j]):
                prevThickness = -1
                prevLen = 0
                continue
            if j - 1 >= 0 and grid[i][j] == grid[i][j - 1] and (grid[i2][j] == grid[i2][j - 1]) and (grid[i3][j] == grid[i3][j - 1]) and (prevThickness == currThickness):
                prevLen += 1
            else:
                prevThickness = currThickness
                prevLen = 1
            ans += prevLen
    print(ans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x, y):
    print('? {} {}'.format(x, y))
    sys.stdout.flush()
    return int(input())

def answerInteractive(i1, j1, i2, j2):
    print('! {} {} {} {}'.format(i1, j1, i2, j2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
for _abc in range(1):
    main()

Solution (Python):
from __future__ import division
import copy
import random
import heapq
import math
import sys
import bisect
import re
import time
from functools import reduce
import datetime
from functools import lru_cache
from collections import deque
from collections import Counter
from collections import defaultdict
from itertools import combinations
from itertools import permutations
from itertools import accumulate
from decimal import Decimal, getcontext, MAX_PREC
from types import GeneratorType
from functools import cmp_to_key
inf = float('inf')
sys.setrecursionlimit(10000000)
getcontext().prec = MAX_PREC

class FastIO:

    def __init__(self):
        return

    @staticmethod
    def _read():
        return sys.stdin.readline().strip()

    def read_int(self):
        return int(self._read())

    def read_float(self):
        return float(self._read())

    def read_ints(self):
        return map(int, self._read().split())

    def read_floats(self):
        return map(float, self._read().split())

    def read_ints_minus_one(self):
        return map(lambda x: int(x) - 1, self._read().split())

    def read_list_ints(self):
        return list(map(int, self._read().split()))

    def read_list_floats(self):
        return list(map(float, self._read().split()))

    def read_list_ints_minus_one(self):
        return list(map(lambda x: int(x) - 1, self._read().split()))

    def read_str(self):
        return self._read()

    def read_list_strs(self):
        return self._read().split()

    def read_list_str(self):
        return list(self._read())

    @staticmethod
    def st(x):
        return sys.stdout.write(str(x) + '\n')

    @staticmethod
    def lst(x):
        return sys.stdout.write(' '.join((str(w) for w in x)) + '\n')

    @staticmethod
    def round_5(f):
        res = int(f)
        if f - res >= 0.5:
            res += 1
        return res

    @staticmethod
    def max(a, b):
        return a if a > b else b

    @staticmethod
    def min(a, b):
        return a if a < b else b

    @staticmethod
    def bootstrap(f, stack=[]):

        def wrappedfunc(*args, **kwargs):
            if stack:
                return f(*args, **kwargs)
            else:
                to = f(*args, **kwargs)
                while True:
                    if isinstance(to, GeneratorType):
                        stack.append(to)
                        to = next(to)
                    else:
                        stack.pop()
                        if not stack:
                            break
                        to = stack[-1].send(to)
                return to
        return wrappedfunc

class SparseTable1:

    def __init__(self, lst, fun='max'):
        self.fun = fun
        self.n = len(lst)
        self.lst = lst
        self.f = [[0] * (int(math.log2(self.n)) + 1) for _ in range(self.n + 1)]
        self.gen_sparse_table()
        return

    def gen_sparse_table(self):
        for i in range(1, self.n + 1):
            self.f[i][0] = self.lst[i - 1]
        for j in range(1, int(math.log2(self.n)) + 1):
            for i in range(1, self.n - (1 << j) + 2):
                a = self.f[i][j - 1]
                b = self.f[i + (1 << j - 1)][j - 1]
                if self.fun == 'max':
                    self.f[i][j] = a if a > b else b
                elif self.fun == 'min':
                    self.f[i][j] = a if a < b else b
                elif self.fun == 'gcd':
                    self.f[i][j] = math.gcd(a, b)
                elif self.fun == 'and':
                    self.f[i][j] = a & b
                elif self.fun == 'or':
                    self.f[i][j] = a | b
        return

    def query(self, left, right):
        k = int(math.log2(right - left + 1))
        a = self.f[left][k]
        b = self.f[right - (1 << k) + 1][k]
        if self.fun == 'max':
            return a if a > b else b
        elif self.fun == 'min':
            return a if a < b else b
        elif self.fun == 'gcd':
            return math.gcd(a, b)
        elif self.fun == 'and':
            return a & b
        elif self.fun == 'or':
            return a | b

def main(ac=FastIO()):
    (m, n) = ac.read_ints()
    grid = [ac.read_str() for _ in range(m)]
    left = [0] * m
    ans = 0
    for j in range(n):
        for i in range(m):
            if j == 0 or grid[i][j - 1] == grid[i][j]:
                left[i] += 1
            else:
                left[i] = 1
        lst = []
        pre = grid[0][j]
        cnt = 1
        for i in range(1, m):
            if grid[i][j] == pre:
                cnt += 1
            else:
                lst.append([i - cnt, i - 1, cnt])
                cnt = 1
                pre = grid[i][j]
        lst.append([n - cnt, n - 1, cnt])
        k = len(lst)
        for x in range(1, k - 1):
            if lst[x][-1] <= lst[x - 1][-1] and lst[x][-1] <= lst[x + 1][-1]:
                (up, down, h) = lst[x]
                ans += min(left[up - h:down + h + 1])
    ac.st(ans)
    return
main()

Solution (Python):
from itertools import groupby
(n, m) = map(int, input().split())
g = [input() for _ in range(n)]
s = ['.'] * n
cnt = [0] * n
ans = 0
for j in range(m):
    for i in range(n):
        if g[i][j] != s[i]:
            cnt[i] = 0
            s[i] = g[i][j]
        cnt[i] += 1
    gp = [(ch, len(list(it))) for (ch, it) in groupby(s)]
    l = gp[0][1]
    for i in range(1, len(gp) - 1):
        (ch, cc) = gp[i]
        if gp[i - 1][1] >= cc and gp[i + 1][1] >= cc:
            ans += min(cnt[l - cc:l + cc * 2])
        l += cc
print(ans)