3529. Count Cells in Overlapping Horizontal and Vertical Substrings LeetCode Solution
In this guide, you will get 3529. Count Cells in Overlapping Horizontal and Vertical Substrings LeetCode Solution with the best time and space complexity. The solution to Count Cells in Overlapping Horizontal and Vertical Substrings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Count Cells in Overlapping Horizontal and Vertical Substrings solution in C++
- Count Cells in Overlapping Horizontal and Vertical Substrings solution in Java
- Count Cells in Overlapping Horizontal and Vertical Substrings solution in Python
- Additional Resources
Problem Statement of Count Cells in Overlapping Horizontal and Vertical Substrings
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.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.
Complexity Analysis
- Time Complexity: O(mn)
- Space Complexity: O(mn)
3529. Count Cells in Overlapping Horizontal and Vertical Substrings LeetCode Solution in C++
class Solution {
public:
int countCells(vector<vector<char>>& grid, string pattern) {
const int m = grid.size();
const int n = grid[0].size();
int ans = 0;
string flattendGridRow;
string flattendGridCol;
// Flatten the grid for horizontal matching.
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
flattendGridRow += grid[i][j];
// Flatten the grid for vertical matching.
for (int j = 0; j < n; ++j)
for (int i = 0; i < m; ++i)
flattendGridCol += grid[i][j];
// Find matching positions.
const vector<vector<bool>> horizontalMatches =
markMatchedCells(flattendGridRow, pattern, m, n, true);
const vector<vector<bool>> verticalMatches =
markMatchedCells(flattendGridCol, pattern, m, n, false);
// Count overlapping match positions.
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (horizontalMatches[i][j] && verticalMatches[i][j])
++ans;
return ans;
}
private:
static constexpr long kBase = 13;
static constexpr long kHash = 1'000'000'007;
vector<vector<bool>> markMatchedCells(const string& flattenedGrid,
const string& pattern, int m, int n,
bool isHorizontal) {
vector<vector<bool>> matchMatrix(m, vector<bool>(n, false));
vector<int> matchPrefix(flattenedGrid.length() + 1);
vector<long> pows{1}; // pows[i] := kBase^i % kHash
long patternHash = 0;
long runningHash = 0;
for (int i = 1; i < pattern.length(); ++i)
pows.push_back((pows.back() * kBase) % kHash);
for (const char c : pattern)
patternHash = (patternHash * kBase + (c - 'a')) % kHash;
for (int i = 0; i < flattenedGrid.length(); ++i) {
runningHash = (runningHash * kBase + (flattenedGrid[i] - 'a')) % kHash;
if (i >= pattern.length() - 1) {
if (runningHash == patternHash) { // Match found.
++matchPrefix[i - pattern.length() + 1];
--matchPrefix[i + 1];
}
// Remove the contribution of the oldest letter.
const long oldestLetterHash =
(pows[pattern.length() - 1] *
(flattenedGrid[i - pattern.length() + 1] - 'a')) %
kHash;
runningHash = (runningHash - oldestLetterHash + kHash) % kHash;
}
}
for (int k = 0; k < flattenedGrid.length(); ++k) {
matchPrefix[k] += (k > 0) ? matchPrefix[k - 1] : 0;
if (matchPrefix[k] > 0) {
const int i = isHorizontal ? k / n : k % m;
const int j = isHorizontal ? k % n : k / m;
matchMatrix[i][j] = true;
}
}
return matchMatrix;
}
};
/* code provided by PROGIEZ */3529. Count Cells in Overlapping Horizontal and Vertical Substrings LeetCode Solution in Java
class Solution {
public int countCells(char[][] grid, String pattern) {
final int m = grid.length;
final int n = grid[0].length;
int ans = 0;
StringBuilder flattenedGridRow = new StringBuilder();
StringBuilder flattenedGridCol = new StringBuilder();
// Flatten the grid for horizontal matching.
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
flattenedGridRow.append(grid[i][j]);
// Flatten the grid for vertical matching.
for (int j = 0; j < n; ++j)
for (int i = 0; i < m; ++i)
flattenedGridCol.append(grid[i][j]);
// Find matching positions.
boolean[][] horizontalMatches =
markMatchedCells(flattenedGridRow.toString(), pattern, m, n, true);
boolean[][] verticalMatches =
markMatchedCells(flattenedGridCol.toString(), pattern, m, n, false);
// Count overlapping match positions.
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (horizontalMatches[i][j] && verticalMatches[i][j])
++ans;
return ans;
}
private static final long BASE = 13;
private static final long HASH = 1_000_000_007;
private boolean[][] markMatchedCells(final String flattenedGrid, final String pattern, int m,
int n, boolean isHorizontal) {
boolean[][] matchMatrix = new boolean[m][n];
int[] matchPrefix = new int[flattenedGrid.length() + 1];
long[] pows = new long[pattern.length()]; // pows[i] := BASE^i % HASH
pows[0] = 1;
long patternHash = 0;
long runningHash = 0;
for (int i = 1; i < pattern.length(); ++i)
pows[i] = (pows[i - 1] * BASE) % HASH;
for (final char c : pattern.toCharArray())
patternHash = (patternHash * BASE + (c - 'a')) % HASH;
for (int i = 0; i < flattenedGrid.length(); ++i) {
runningHash = (runningHash * BASE + (flattenedGrid.charAt(i) - 'a')) % HASH;
if (i >= pattern.length() - 1) {
if (runningHash == patternHash) { // Match found.
++matchPrefix[i - pattern.length() + 1];
--matchPrefix[i + 1];
}
// Remove the contribution of the oldest letter.
final long oldestLetterHash =
(pows[pattern.length() - 1] * (flattenedGrid.charAt(i - pattern.length() + 1) - 'a')) %
HASH;
runningHash = (runningHash - oldestLetterHash + HASH) % HASH;
}
}
for (int k = 0; k < flattenedGrid.length(); ++k) {
matchPrefix[k] += (k > 0) ? matchPrefix[k - 1] : 0;
if (matchPrefix[k] > 0) {
final int i = isHorizontal ? k / n : k % m;
final int j = isHorizontal ? k % n : k / m;
matchMatrix[i][j] = true;
}
}
return matchMatrix;
}
}
// code provided by PROGIEZ3529. Count Cells in Overlapping Horizontal and Vertical Substrings LeetCode Solution in Python
class Solution:
def countCells(self, grid: list[list[str]], pattern: str) -> int:
BASE = 13
HASH = 1_000_000_007
m = len(grid)
n = len(grid[0])
def markMatchedCells(flattenedGrid: str, isHorizontal: bool) -> list[list[bool]]:
matchMatrix = [[False] * n for _ in range(m)]
matchPrefix = [0] * (len(flattenedGrid) + 1)
pows = [1] # pows[i] := BASE^i % HASH
patternHash = 0
runningHash = 0
for i in range(1, len(pattern)):
pows.append((pows[-1] * BASE) % HASH)
for c in pattern:
patternHash = (patternHash * BASE + (ord(c) - ord('a'))) % HASH
for i in range(len(flattenedGrid)):
runningHash = (
runningHash * BASE + (ord(flattenedGrid[i]) - ord('a'))) % HASH
if i >= len(pattern) - 1:
if runningHash == patternHash: # Match found.
matchPrefix[i - len(pattern) + 1] += 1
matchPrefix[i + 1] -= 1
# Remove the contribution of the oldest letter.
oldestLetterHash = (
pows[len(pattern) - 1] *
(ord(flattenedGrid[i - len(pattern) + 1]) - ord('a'))) % HASH
runningHash = (runningHash - oldestLetterHash + HASH) % HASH
for k in range(len(flattenedGrid)):
if k > 0:
matchPrefix[k] += matchPrefix[k - 1]
if matchPrefix[k] > 0:
i = k // n if isHorizontal else k % m
j = k % n if isHorizontal else k // m
matchMatrix[i][j] = True
return matchMatrix
# Find matching positions.
flattenedGridRow = ''.join(cell for row in grid for cell in row)
flattenedGridCol = ''.join(cell for col in zip(*grid) for cell in col)
horizontalMatches = markMatchedCells(flattenedGridRow, True)
verticalMatches = markMatchedCells(flattenedGridCol, False)
return sum(horizontalMatches[i][j] and verticalMatches[i][j]
for i in range(m)
for j in range(n))
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.