Count Cells in Overlapping Horizontal and Vertical Substrings - Solution & Explanation
Problem Statement
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:
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:
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:
Input: grid = [["a"]], pattern = "a"
Output: 1
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 10001 <= m * n <= 1051 <= pattern.length <= m * ngridandpatternconsist of only lowercase English letters.
Approach Overview
Problem Overview: You are given a character matrix and two target strings. One string must appear horizontally in rows and the other vertically in columns. The goal is to count how many cells belong to both a valid horizontal substring match and a vertical substring match at the same time.
Approach 1: Brute Force Substring Scanning (O(m * n * k) time, O(m * n) space)
Iterate through every row and check every possible starting position where the horizontal string could fit. Compare characters one by one to confirm the substring. Mark each cell that belongs to a successful horizontal match. Repeat the same process for columns to detect vertical matches. Maintain two boolean matrices to track marked cells, then count positions where both matrices are true. This approach is straightforward but expensive because each candidate substring requires a full character comparison.
Approach 2: Rolling Hash String Matching (O(m * n) time, O(m * n) space)
Use a rolling hash (Rabin–Karp style) to detect substring matches efficiently across rows and columns. Precompute the hash of the horizontal and vertical target strings. For each row, maintain a sliding hash window of length k and update it in constant time as the window moves. When the hash matches the target hash, verify the substring and mark the cells involved. Repeat the same sliding window technique for each column to detect vertical matches. Finally, scan the grid and count cells marked by both passes.
The key insight is that rolling hash removes repeated character comparisons. Instead of checking k characters at every position, the algorithm updates the hash in O(1) time while sliding across the grid. This reduces the total work from substring-by-substring comparisons to linear scans over the matrix.
Implementation relies on concepts from string processing, rolling hash, and matrix traversal. The grid is scanned twice: once row-wise and once column-wise. A boolean matrix records cells participating in horizontal matches, another for vertical matches.
Recommended for interviews: The rolling hash approach is the expected solution. Brute force demonstrates baseline understanding of substring search, but interviewers typically look for the optimized string matching strategy that reduces repeated comparisons and achieves near O(mn) runtime.
Solutions for this problem are being prepared.
Try solving it yourselfDetailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring Scan | O(m * n * k) | O(m * n) | Good for small grids or when implementing the simplest correct solution |
| Rolling Hash (Rabin–Karp) | O(m * n) | O(m * n) | Preferred for large matrices and interview settings where efficient substring matching is required |
Video Solution
Leetcode 3529 | Count Cells in Overlapping Horizontal and Vertical Substrings | Biweekly Contest 155 • Road To FAANG • 408 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Count Cells in Overlapping Horizontal and Vertical Substrings easy or hard?
Count Cells in Overlapping Horizontal and Vertical Substrings Python/Java solution
How to solve Count Cells in Overlapping Horizontal and Vertical Substrings in O(n)?
What is the best approach for Count Cells in Overlapping Horizontal and Vertical Substrings?
Is Count Cells in Overlapping Horizontal and Vertical Substrings asked at Google/Amazon/Meta?
What data structure is used in Count Cells in Overlapping Horizontal and Vertical Substrings?
What is the time complexity of Count Cells in Overlapping Horizontal and Vertical Substrings?
Ready to solve this problem?
Practice Count Cells in Overlapping Horizontal and Vertical Substrings with our built-in code editor and test cases.
Practice on FleetCode