<p>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 <span data-keyword="submatrix">submatrices</span> that contain:</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

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

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p><strong><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;" /></strong></p>
</div>

<p><strong class="example">Example 2:</strong></p>

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

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[&quot;.&quot;,&quot;.&quot;],[&quot;.&quot;,&quot;.&quot;]]</span></p>

<p><strong>Output:</strong> <span class="example-io">0</span></p>

<p><strong>Explanation:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<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>

class Solution:
    def numberOfSubmatrices(self, grid: List[List[str]]) -> int:
        # dictionary and counter of 'X' and 'Y'
        # keep counter of 'X', 'Y' and '.' for each row r separately upto column j
        # replace 'X' by 1, 'Y' by -1, and '.' by 0, condition count 'X' equal 'Y' is sum to be 0
        # mapping[(r, c)] a tuple with for each row separately, sum upto col c and if 'X' present
        def charMap(char):
            if char == 'X':
                return 1
            elif char == 'Y':
                return -1
            else:
                return 0

        mapping = dict() 
        mapping[(0, 0)] = (charMap(grid[0][0]), grid[0][0]=="X")
        result = 0

        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if c==0:
                    mapping[(r, 0)] = (charMap(grid[r][0]), grid[r][0]=="X")
                else:
                    char = grid[r][c]
                    value, hasX = mapping[(r, c-1)]
                    hasX = hasX or char=="X"
                    value += charMap(char)
                    mapping[(r, c)] = (value, hasX)
                    
        # print(mapping)
        for c in range(len(grid[0])):
            value, hasX = mapping[(0, c)]
            # print(0, c, countxy)
            if (hasX) and (value==0):
                result += 1
            for r in range(1, len(grid)):
                localval, localHasX = mapping[(r, c)]
                value += localval
                hasX = hasX or localHasX
                # print(r, c, countxy)
                if (hasX) and (value==0):
                    result += 1
        return result
# TC: O(N^2)
# SC: O(N^2)
208039