3212. Count Submatrices With Equal Frequency of X and Y
Given a 2D character matrix grid, where grid[i][j] is either 'X', 'Y', or '.', return the number of submatrices that contains:
grid[0][0]- an equal frequency of
'X' and 'Y'.
- at least one
'X'.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public:
int numberOfSubmatrices(vector<vector<char>>& A) {
int n = A.size(), m = A[0].size(), res = 0;
vector<pair<int,int>> dp(m);
for(auto& vec : A) {
int sum = 0, fl = 0;
for(int i = 0; i < m; i++) {
if(vec[i] == 'X') {
fl = 1;
sum++;
} else if(vec[i] == 'Y') {
sum--;
}
dp[i].first |= fl;
dp[i].second += sum;
if(dp[i].first and dp[i].second == 0) res++;
}
}
return res;
}
};
|
