count-submatrices-with-equal-frequency-of-x-and-y

java

python3

python

javascript

typescript

csharp

golang

kotlin

swift

rust

ruby

dart

scala

elixir

erlang

racket

bash

mysql

mssql

postgresql

oraclesql

pythondata

Algorithms

Given a 2D character matrix <code>grid</code>, where <code>grid[i][j]</code> is either <code>&#39;X&#39;</code>, <code>&#39;Y&#39;</code>, or <code>&#39;.&#39;</code>, return the number of submatrices that contain:

<ul>
	<li><code>grid[0][0]</code></li>
	<li>an equal frequency of <code>&#39;X&#39;</code> and <code>&#39;Y&#39;</code>.</li>
	<li>at least one <code>&#39;X&#39;</code>.</li>
</ul>

&nbsp;
Example 1:

<div class="example-block">
Input: grid = [[&quot;X&quot;,&quot;Y&quot;,&quot;.&quot;],[&quot;Y&quot;,&quot;.&quot;,&quot;.&quot;]]

Output: 3

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/06/07/examplems.png" style="padding: 10px; background: rgb(255, 255, 255); border-radius: 0.5rem; width: 175px; height: 350px;" />
</div>

Example 2:

<div class="example-block">
Input: grid = [[&quot;X&quot;,&quot;X&quot;],[&quot;X&quot;,&quot;Y&quot;]]

Output: 0

Explanation:

No submatrix has an equal frequency of <code>&#39;X&#39;</code> and <code>&#39;Y&#39;</code>.
</div>

Example 3:

<div class="example-block">
Input: grid = [[&quot;.&quot;,&quot;.&quot;],[&quot;.&quot;,&quot;.&quot;]]

Output: 0

Explanation:

No submatrix has at least one <code>&#39;X&#39;</code>.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= grid.length, grid[i].length &lt;= 1000</code></li>
	<li><code>grid[i][j]</code> is either <code>&#39;X&#39;</code>, <code>&#39;Y&#39;</code>, or <code>&#39;.&#39;</code>.</li>
</ul>