7000.All Letter Subgrid Count I

Time Limit: 1s Memory Limit: 512MB

You are given a grid of letters. Your task is to calculate the number of square subgrids that contain all the letters.

Input Format(From the terminal/stdin)

The first line has two integers $n$ and $k$ : the size of the grid and the number of letters. The letters are the first $k$ uppercase letters.

After this, there are $n$ lines that describe the grid. Each line has $n$ letters.

  • $1 \le n \le 3000$
  • $1 \le k \le 26$

Output Format(To the terminal/stdout)

Print the number of subgrids.

Sample Input

Copy
5 3
ABBBC
BBBBC
BCAAA
AAAAA
AAAAA
 · \n
     \n
     \n
     \n
     \n
     \n

Sample Output

Copy
15
  \n
Source: CSES, Counting Problems, 3415

Submit

请先 登录

© 2025 FAQs