Count Cells in Overlapping Horizontal and Vertical Substrings

To solve this problem, scan the grid for all horizontal and vertical matches of the pattern using string hashing or pattern matching. Track the cells covered by both orientations and count their overlaps. This approach minimizes redundant searches and leverages rolling hash techniques for fast substring comparisons in the matrix.

Problem Statement

You are given an m x n character matrix and a string pattern. A horizontal substring reads left to right, wrapping to the next row if necessary, without wrapping from the last row to the first. Count the cells that appear in both horizontal and vertical occurrences of the pattern.

A vertical substring reads top to bottom, wrapping to the next column if needed, without wrapping from the last column to the first. Determine how many unique cells in the grid are part of at least one horizontal and one vertical substring matching the given pattern.

Examples

Example 1

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

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

Input: grid = [["c","a","a","a"],["a","a","b","a"],["b","b","a","a"],["a","a","b","a"]], pattern = "aba"

Output: 4

The cells colored above are all part of at least one horizontal and one vertical substring matching the pattern "aba" .

Example 3

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

Output: 1

Example details omitted.

Constraints

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

Solution Approach

Use Rolling Hash for Horizontal Matches

Compute rolling hashes for each row concatenated with the next row to handle wrapping. Compare hashes against the pattern hash to identify horizontal substring positions quickly.

Use Rolling Hash for Vertical Matches

Treat each column concatenated with the next column similarly. Compute rolling hashes vertically to locate substring matches without excessive iteration, accounting for vertical wrapping rules.

Combine and Count Overlapping Cells

Store coordinates of horizontal and vertical matches in two sets. Iterate through one set and count the cells also present in the other set to determine the final number of overlapping cells.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the rolling hash implementation, typically O(m n) for scanning all rows and columns. Space complexity is O(m n) to store match coordinates for horizontal and vertical occurrences.

What Interviewers Usually Probe

• Are you considering pattern matching optimization for large grids?
• Can you handle wrapping logic in both horizontal and vertical directions efficiently?
• How will you track overlapping cells without redundant computation?

Common Pitfalls or Variants

Common pitfalls

• Forgetting to wrap rows or columns correctly when scanning substrings.
• Counting a cell multiple times if it appears in multiple matches in one orientation.
• Ignoring edge cases when pattern length exceeds row or column segments.

Follow-up variants

• Count cells for multiple patterns simultaneously using the same rolling hash approach.
• Modify the grid to allow toroidal wrapping and count overlapping cells under new rules.
• Count overlapping cells only for non-overlapping horizontal and vertical substrings.

FAQ

What is the key pattern in Count Cells in Overlapping Horizontal and Vertical Substrings?

The key pattern is finding cells that are part of both horizontal and vertical occurrences of the given string pattern in the grid.

Can rolling hash handle both horizontal and vertical substrings?

Yes, rolling hash can be applied row-wise and column-wise to efficiently detect all substring matches.

How do I handle wrapping across rows or columns?

Concatenate the next row or column as needed when the substring extends past the end, ensuring you do not wrap back to the first row or column.

What is the time complexity for large grids?

Using rolling hash, scanning all rows and columns is typically O(m*n), which handles the constraints efficiently.

How can I avoid double counting cells?

Store horizontal and vertical match coordinates in separate sets and count only the cells present in both sets.