Problem

You are given an m x n matrix grid consisting of characters and a string pattern.

A horizontal substring is a contiguous sequence of characters read from left to right. If the end of a row is reached before the substring is complete, it wraps to the first column of the next row and continues as needed. You do not wrap from the bottom row back to the top.

A vertical substring is a contiguous sequence of characters read from top to bottom. If the bottom of a column is reached before the substring is complete, it wraps to the first row of the next column and continues as needed. You do not wrap from the last column back to the first.

Count the number of cells in the matrix that satisfy the following condition:

  • The cell must be part of at least one horizontal substring and at least one vertical substring, where both substrings are equal to the given pattern.

Return the count of these cells.

Example 1

1
2
3
4
5
6
7
8
9

![](https://assets.leetcode.com/uploads/2025/03/03/gridtwosubstringsdrawio.png)
Input: grid =
[["a","a","c","c"],["b","b","b","c"],["a","a","b","a"],["c","a","a","c"],["a","a","b","a"]],
pattern = "abaca"
Output: 1
Explanation:
The pattern `"abaca"` appears once as a horizontal substring (colored blue)
and once as a vertical substring (colored red), intersecting at one cell
(colored purple).

Example 2

1
2
3
4
5
6
7
8

![](https://assets.leetcode.com/uploads/2025/03/03/gridexample2fixeddrawio.png)
Input: grid =
[["c","a","a","a"],["a","a","b","a"],["b","b","a","a"],["a","a","b","a"]],
pattern = "aba"
Output: 4
Explanation:
The cells colored above are all part of at least one horizontal and one
vertical substring matching the pattern `"aba"`.

Example 3

1
2

Input: grid = [["a"]], pattern = "a"
Output: 1

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 1000
  • 1 <= m * n <= 10^5
  • 1 <= pattern.length <= m * n
  • grid and pattern consist of only lowercase English letters.

Examples

Solution

Method 1 – Rolling Hash and Set Marking 1

Intuition

To efficiently find all horizontal and vertical substrings matching the pattern (with wrapping), we use rolling hash for substring matching. For each match, we mark the cells covered by the substring. Finally, we count the cells that are covered by at least one horizontal and at least one vertical match.

Approach

  1. Use rolling hash to find all horizontal substrings matching the pattern (with wrapping across rows).
  2. Use rolling hash to find all vertical substrings matching the pattern (with wrapping across columns).
  3. For each match, mark the cells covered by the substring in two boolean matrices: one for horizontal, one for vertical.
  4. Count the number of cells that are marked in both matrices.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution:
    def countCells(self, grid: list[list[str]], pattern: str) -> int:
        m, n = len(grid), len(grid[0])
        k = len(pattern)
        hcover = [[False]*n for _ in range(m)]
        vcover = [[False]*n for _ in range(m)]
        # Horizontal substrings
        for i in range(m):
            s = ''.join(grid[i])
            s2 = s + ''.join(grid[(i+1)%m]) if k > n else s
            for start in range(n):
                chars = []
                for t in range(k):
                    row = (i + (start + t) // n)
                    col = (start + t) % n
                    if row >= m:
                        break
                    chars.append(grid[row][col])
                if len(chars) == k and ''.join(chars) == pattern:
                    for t in range(k):
                        row = (i + (start + t) // n)
                        col = (start + t) % n
                        hcover[row][col] = True
        # Vertical substrings
        for j in range(n):
            colstr = ''.join(grid[x][j] for x in range(m))
            colstr2 = colstr + ''.join(grid[x][(j+1)%n] for x in range(m)) if k > m else colstr
            for start in range(m):
                chars = []
                for t in range(k):
                    col = (j + (start + t) // m)
                    row = (start + t) % m
                    if col >= n:
                        break
                    chars.append(grid[row][col])
                if len(chars) == k and ''.join(chars) == pattern:
                    for t in range(k):
                        col = (j + (start + t) // m)
                        row = (start + t) % m
                        vcover[row][col] = True
        # Count cells covered by both
        ans = 0
        for i in range(m):
            for j in range(n):
                if hcover[i][j] and vcover[i][j]:
                    ans += 1
        return ans

Complexity

  • ⏰ Time complexity: O(mn * k), where m, n are grid dimensions and k is the pattern length, as we check all possible starting positions for both directions.
  • 🧺 Space complexity: O(mn), for the marking matrices.